C/자료구조와 알고리듬
Chapter 15. BFS
GameStudy
2021. 12. 2. 19:44
Def) 너비 우선 탐색(BFS, Breadth First Search)
- 현재 정점과 인접한 모든 정점을 방문한 후, 다시 이들 정점과 인접한
모든 정점을 찾아 방문하는 방식.
- 시작 정점으로부터 가까운 정점을 먼저 방문하고,
멀리 떨어진 정점을 나중에 방문.
- 보통 큐를 이용하여 구현
Thm) BFS 구현 With 큐
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 101,
};
typedef struct queue {
int nArray[MAX_COUNT];
size_t uCnt;
size_t uFront;
size_t uRear;
} queue_t;
void enqueue(queue_t* _pQueue, int _nData);
int isEmpty(queue_t* _pQueue);
int dequeue(queue_t* _pQueue);
int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT] = {0,};
size_t g_uVCnt, g_uECnt;
queue_t g_queue;
void BFS(int _nStartV);
int main(void)
{
size_t i, uV1, uV2, uStartV = 1;
scanf("%zu %zu", &g_uVCnt, &g_uECnt);
for (i = 1; i <= g_uECnt; ++i)
{
scanf("%zu %zu", &uV1, &uV2);
g_nAdjMat[uV1][uV2] = TRUE;
g_nAdjMat[uV2][uV1] = TRUE;
}
BFS(uStartV);
return 0;
}
void enqueue(queue_t* _pQueue, int _nData)
{
assert(_pQueue->uCnt < MAX_COUNT);
_pQueue->nArray[_pQueue->uRear] = _nData;
_pQueue->uRear = (_pQueue->uRear + 1) % MAX_COUNT;
++_pQueue->uCnt;
}
int isEmpty(queue_t* _pQueue)
{
if (0 == _pQueue->uCnt) return TRUE;
return FALSE;
}
int dequeue(queue_t* _pQueue)
{
int ret;
assert(FALSE == isEmpty(_pQueue));
ret = _pQueue->nArray[_pQueue->uFront];
_pQueue->uFront = (_pQueue->uFront + 1) % MAX_COUNT;
--_pQueue->uCnt;
return ret;
}
void BFS(int _nStartV)
{
size_t i;
g_nVisitMat[_nStartV] = TRUE;
enqueue(&g_queue, _nStartV);
printf("%d에서 시작\n", _nStartV);
while (FALSE == isEmpty(&g_queue))
{
int nCurrV = dequeue(&g_queue);
for (i = 1; i <= g_uVCnt; ++i)
{
if (FALSE == g_nVisitMat[i] && TRUE == g_nAdjMat[nCurrV][i])
{
g_nVisitMat[nCurrV] = TRUE;
enqueue(&g_queue, (int)i);
printf("%d -> %zu\n", nCurrV, i);
}
}
}
}<hide/>
// TestCase1
4 4
1 2
1 3
2 4
3 4
// Expected
1에서 시작
1에서 2로 이동
1에서 3로 이동
2에서 4로 이동
// TestCase1
6 9
1 2
1 3
2 4
2 5
3 4
3 6
4 5
4 6
5 6
// Expected
1에서 시작
1에서 2로 이동
1에서 3로 이동
2에서 4로 이동
2에서 5로 이동
3에서 6로 이동
Ex) DFS Vs. BFS
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 256
};
typedef struct queue {
int nArray[MAX_COUNT];
size_t uCnt;
size_t uFront;
size_t uRear;
} queue_t;
void enqueue(queue_t* _pQueue, int _nData);
int isEmpty(queue_t* _pQueue);
int dequeue(queue_t* _pQueue);
int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT] = {0,};
size_t g_uVCnt, g_uECnt;
queue_t g_queue;
void BFS(int _nStartV);
void DFS(int _nCurrV);
int main(void)
{
int i, j;
char uV1, uV2, uStartV;
scanf("%zu %zu", &g_uVCnt, &g_uECnt);
getchar();
for (i = 1; i <= g_uECnt; ++i)
{
scanf("%c %c", &uV1, &uV2);
getchar();
uV1 -= 'A';
uV2 -= 'A';
g_nAdjMat[uV1][uV2] = TRUE;
g_nAdjMat[uV2][uV1] = TRUE;
}
scanf("%c", &uStartV);
uStartV -= 'A';
DFS(uStartV);
printf("\n");
for (i = 1; i <= g_uVCnt; ++i) g_nVisitMat[i] = FALSE;
BFS(uStartV);
/*
printf("%zu %zu", g_uVCnt, g_uECnt);
for (i = 1; i <= g_uVCnt; ++i)
{
for (j = 1; j <= g_uVCnt; ++j)
{
printf("%d ", g_nAdjMat[i][j]);
}
printf("\n");
}
printf("%c", uStartV);
*/
return 0;
}
void enqueue(queue_t* _pQueue, int _nData)
{
assert(_pQueue->uCnt < MAX_COUNT);
_pQueue->nArray[_pQueue->uRear] = _nData;
_pQueue->uRear = (_pQueue->uRear + 1) % MAX_COUNT;
++_pQueue->uCnt;
}
int isEmpty(queue_t* _pQueue)
{
if (0 == _pQueue->uCnt) return TRUE;
return FALSE;
}
int dequeue(queue_t* _pQueue)
{
int ret;
assert(FALSE == isEmpty(_pQueue));
ret = _pQueue->nArray[_pQueue->uFront];
_pQueue->uFront = (_pQueue->uFront + 1) % MAX_COUNT;
--_pQueue->uCnt;
return ret;
}
void BFS(int _nStartV)
{
int i;
g_nVisitMat[_nStartV] = TRUE;
enqueue(&g_queue, _nStartV);
printf("%c", _nStartV + 'A');
while (FALSE == isEmpty(&g_queue))
{
int nCurrV = dequeue(&g_queue);
for (i = 1; i <= g_uVCnt; ++i)
{
if (FALSE == g_nVisitMat[i] && TRUE == g_nAdjMat[nCurrV][i])
{
g_nVisitMat[i] = TRUE;
enqueue(&g_queue, i);
printf("%c", i + 'A');
}
}
}
}
void DFS(int _nCurrV)
{
size_t i;
g_nVisitMat[_nCurrV] = TRUE;
printf("%c", _nCurrV + 'A');
for (i = 1; i <= g_uVCnt; ++i)
{
if (FALSE == g_nVisitMat[i] && TRUE == g_nAdjMat[_nCurrV][i])
{
DFS(i);
}
}
}<hide/>
// TestCase1
7 9
A B
B E
A E
B C
B F
C F
C D
D G
G F
A
// Expected
ABCDGFE
ABECFDG
Ex) 바이러스
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 101
};
typedef struct queue {
int nArray[MAX_COUNT];
size_t uCnt;
size_t uFront;
size_t uRear;
} queue_t;
void enqueue(queue_t* _pQueue, int _nData);
int isEmpty(queue_t* _pQueue);
int dequeue(queue_t* _pQueue);
int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT] = {0,};
size_t g_uVCnt, g_uECnt, g_uInfectCnt;
queue_t g_queue;
void BFS(int _nStartV);
int main(void)
{
size_t i, uV1, uV2;
scanf("%zu %zu", &g_uVCnt, &g_uECnt);
for (i = 1; i <= g_uECnt; ++i)
{
scanf("%zu %zu", &uV1, &uV2);
g_nAdjMat[uV1][uV2] = TRUE;
g_nAdjMat[uV2][uV1] = TRUE;
}
BFS(1);
printf("%zu", g_uInfectCnt);
return 0;
}
void enqueue(queue_t* _pQueue, int _nData)
{
assert(_pQueue->uCnt < MAX_COUNT);
_pQueue->nArray[_pQueue->uRear] = _nData;
_pQueue->uRear = (_pQueue->uRear + 1) % MAX_COUNT;
++_pQueue->uCnt;
}
int isEmpty(queue_t* _pQueue)
{
if (0 == _pQueue->uCnt) return TRUE;
return FALSE;
}
int dequeue(queue_t* _pQueue)
{
int ret;
assert(FALSE == isEmpty(_pQueue));
ret = _pQueue->nArray[_pQueue->uFront];
_pQueue->uFront = (_pQueue->uFront + 1) % MAX_COUNT;
--_pQueue->uCnt;
return ret;
}
void BFS(int _nStartV)
{
int i;
g_nVisitMat[_nStartV] = TRUE;
enqueue(&g_queue, _nStartV);
while (FALSE == isEmpty(&g_queue))
{
int nCurrV = dequeue(&g_queue);
for (i = 1; i <= g_uVCnt; ++i)
{
if (FALSE == g_nVisitMat[i] && TRUE == g_nAdjMat[nCurrV][i])
{
g_nVisitMat[i] = TRUE;
enqueue(&g_queue, i);
++g_uInfectCnt;
}
}
}
}<hide/>
// TestCase1
7
6
1 2
2 3
1 5
5 2
5 6
4 7
// Expected
4
Note) 2차원 맵 탐색을 위한 BFS
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 101,
DIRECTION = 4
};
typedef struct queue {
int nArray[MAX_COUNT][2];
size_t nCnt;
size_t nFront;
size_t nRear;
} queue_t;
void enqueue(queue_t* _pQueue, int _nData1, int _nData2);
int isEmpty(queue_t* _pQueue);
int* dequeue(queue_t* _pQueue);
int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT][MAX_COUNT] = {0,};
size_t g_uVRowCnt, g_uVColCnt;
queue_t g_queue = {0,};
int g_nDirMat[DIRECTION][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
void BFS(int _nStartVRow, int _nStartVCol);
int main(void)
{
size_t i, j, uCnt = 0;
scanf("%zu %zu", &g_uVColCnt, &g_uVRowCnt);
for (i = 1; i <= g_uVRowCnt; ++i)
{
for (j = 1; j <= g_uVColCnt; ++j)
{
scanf("%d", &g_nAdjMat[i][j]);
}
}
for (i = 1; i <= g_uVRowCnt; ++i)
{
for (j = 1; j <= g_uVColCnt; ++j)
{
if (FALSE == g_nVisitMat[i][j] && TRUE == g_nAdjMat[i][j])
{
++uCnt;
BFS(i, j);
}
}
}
printf("%zu", uCnt);
return 0;
}
void enqueue(queue_t* _pQueue, int _nData1, int _nData2)
{
assert(_pQueue->nCnt < MAX_COUNT);
_pQueue->nArray[_pQueue->nRear][0] = _nData1;
_pQueue->nArray[_pQueue->nRear][1] = _nData2;
_pQueue->nRear = (_pQueue->nRear + 1) % MAX_COUNT;
++_pQueue->nCnt;
}
int isEmpty(queue_t* _pQueue)
{
if (0 == _pQueue->nCnt) return TRUE;
return FALSE;
}
int* dequeue(queue_t* _pQueue)
{
int* ret;
assert(FALSE == isEmpty(_pQueue));
ret = _pQueue->nArray[_pQueue->nFront];
_pQueue->nFront = (_pQueue->nFront + 1) % MAX_COUNT;
--_pQueue->nCnt;
return ret;
}
void BFS(int _nStartVRow, int _nStartVCol)
{
size_t i, j;
g_nVisitMat[_nStartVRow][_nStartVCol] = TRUE;
enqueue(&g_queue, _nStartVRow, _nStartVCol);
printf("(%d, %d) Start.\n", _nStartVRow, _nStartVCol);
while (FALSE == isEmpty(&g_queue))
{
int* nCurrVArr = dequeue(&g_queue);
int nCurrVRow = nCurrVArr[0];
int nCurrVCol = nCurrVArr[1];
for (i = 0; i < DIRECTION; ++i)
{
int nNextVRow = nCurrVRow + g_nDirMat[i][0];
int nNextVCol = nCurrVCol + g_nDirMat[i][1];
if (TRUE == g_nVisitMat[nNextVRow][nNextVCol]) continue;
if (TRUE == g_nAdjMat[nNextVRow][nNextVCol] &&
1 <= nNextVRow && nNextVRow <= g_uVRowCnt &&
1 <= nNextVCol && nNextVCol <= g_uVColCnt)
{
g_nVisitMat[nNextVRow][nNextVCol] = TRUE;
enqueue(&g_queue, nNextVRow, nNextVCol);
printf("(%d, %d) ->(%d, %d)\n", nCurrVRow, nCurrVCol, nNextVRow, nNextVCol);
}
}
}
}
Ex) 마법의 비료
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <math.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 101,
DIRECTION = 4
};
typedef struct queue {
int nArray[MAX_COUNT][2];
size_t nCnt;
size_t nFront;
size_t nRear;
} queue_t;
void enqueue(queue_t* _pQueue, int _nData1, int _nData2);
int isEmpty(queue_t* _pQueue);
int* dequeue(queue_t* _pQueue);
int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT][MAX_COUNT] = {0,};
size_t g_uVRowCnt, g_uVColCnt, g_uCnt = 0, g_uArea = 0;
queue_t g_queue = {0,};
int g_nDirMat[DIRECTION][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
int g_uAreaArr[MAX_COUNT] = {0,};
void BFS(int _nStartVRow, int _nStartVCol);
int main(void)
{
size_t i, j;
double res = 0;
scanf("%zu %zu", &g_uVColCnt, &g_uVRowCnt);
for (i = 1; i <= g_uVRowCnt; ++i)
{
for (j = 1; j <= g_uVColCnt; ++j)
{
scanf("%d", &g_nAdjMat[i][j]);
}
}
for (i = 1; i <= g_uVRowCnt; ++i)
{
for (j = 1; j <= g_uVColCnt; ++j)
{
if (FALSE == g_nVisitMat[i][j] && TRUE == g_nAdjMat[i][j])
{
++g_uArea;
BFS(i, j);
}
}
}
for (i = 1; i <= g_uArea; ++i)
{
res = res + sqrt((double)g_uAreaArr[i]);
}
printf("%.4lf", res);
return 0;
}
void enqueue(queue_t* _pQueue, int _nData1, int _nData2)
{
assert(_pQueue->nCnt < MAX_COUNT);
_pQueue->nArray[_pQueue->nRear][0] = _nData1;
_pQueue->nArray[_pQueue->nRear][1] = _nData2;
_pQueue->nRear = (_pQueue->nRear + 1) % MAX_COUNT;
++_pQueue->nCnt;
}
int isEmpty(queue_t* _pQueue)
{
if (0 == _pQueue->nCnt) return TRUE;
return FALSE;
}
int* dequeue(queue_t* _pQueue)
{
int* ret;
assert(FALSE == isEmpty(_pQueue));
ret = _pQueue->nArray[_pQueue->nFront];
_pQueue->nFront = (_pQueue->nFront + 1) % MAX_COUNT;
--_pQueue->nCnt;
return ret;
}
void BFS(int _nStartVRow, int _nStartVCol)
{
size_t i, j;
g_nVisitMat[_nStartVRow][_nStartVCol] = TRUE;
enqueue(&g_queue, _nStartVRow, _nStartVCol);
++g_uAreaArr[g_uArea];
while (FALSE == isEmpty(&g_queue))
{
int* nCurrVArr = dequeue(&g_queue);
int nCurrVRow = nCurrVArr[0];
int nCurrVCol = nCurrVArr[1];
for (i = 0; i < DIRECTION; ++i)
{
int nNextVRow = nCurrVRow + g_nDirMat[i][0];
int nNextVCol = nCurrVCol + g_nDirMat[i][1];
if (TRUE == g_nVisitMat[nNextVRow][nNextVCol]) continue;
if (TRUE == g_nAdjMat[nNextVRow][nNextVCol] &&
1 <= nNextVRow && nNextVRow <= g_uVRowCnt &&
1 <= nNextVCol && nNextVCol <= g_uVColCnt)
{
g_nVisitMat[nNextVRow][nNextVCol] = TRUE;
enqueue(&g_queue, nNextVRow, nNextVCol);
++g_uAreaArr[g_uArea];
}
}
}
}<hide/>
// TestCase
5 4
1 1 1 1 0
0 0 0 1 1
1 1 0 0 0
0 0 0 0 1
// Expected
4.8637
Ex) 알리바바 미로
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 101,
DIRECTION = 4
};
typedef struct queue {
int nArray[MAX_COUNT];
size_t uCnt;
size_t uFront;
size_t uRear;
} queue_t;
void enqueue(queue_t* _pQueue, int _nData);
int isEmpty(queue_t* _pQueue);
int dequeue(queue_t* _pQueue);
int g_nAdjMat[MAX_COUNT][MAX_COUNT] = { 0, };
int g_nVisitMat[MAX_COUNT][MAX_COUNT] = { 0, };
size_t g_uVRowCnt, g_uVColCnt, g_uBlockCnt = 0, g_uFinVRow = 1, g_uFinVCol;
int g_nDepth = 0, g_nMinDepth = MAX_COUNT * MAX_COUNT;
int g_nDirMat[DIRECTION][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
queue_t g_qRow, g_qCol, g_qDep;
int g_nBlockMat[MAX_COUNT][MAX_COUNT] = { 0, };
int flag = 0;
void BFS(int _nStartVRow, int _nStartVCol);
int main(void)
{
size_t i, j, uStartVRow = 5, uStartVCol = 1;
scanf("%zu %zu", &g_uVRowCnt, &g_uVColCnt);
g_uFinVCol = g_uVColCnt;
uStartVRow = g_uVRowCnt;
for (i = 1; i <= g_uVRowCnt; ++i)
{
for (j = 1; j <= g_uVColCnt; ++j)
{
scanf("%1d", &g_nAdjMat[i][j]);
}
}
BFS(uStartVRow, uStartVCol);
/*
printf("\n");
for (i = 1; i <= g_uVRowCnt; ++i)
{
for (j = 1; j <= g_uVColCnt; ++j)
{
printf("%2d ", g_nBlockMat[i][j]);
}
printf("\n");
}
*/
if (0 == flag)
{
printf("-1");
return 0;
}
printf("%d", g_nMinDepth + 1);
return 0;
}
void enqueue(queue_t* _pQueue, int _nData)
{
assert(_pQueue->uCnt < MAX_COUNT);
_pQueue->nArray[_pQueue->uRear] = _nData;
_pQueue->uRear = (_pQueue->uRear + 1) % MAX_COUNT;
++_pQueue->uCnt;
}
int isEmpty(queue_t* _pQueue)
{
if (0 == _pQueue->uCnt) return TRUE;
return FALSE;
}
int dequeue(queue_t* _pQueue)
{
int ret;
assert(FALSE == isEmpty(_pQueue));
ret = _pQueue->nArray[_pQueue->uFront];
_pQueue->uFront = (_pQueue->uFront + 1) % MAX_COUNT;
--_pQueue->uCnt;
return ret;
}
void BFS(int _nStartVRow, int _nStartVCol)
{
size_t i;
g_nVisitMat[_nStartVRow][_nStartVCol] = TRUE;
enqueue(&g_qRow, _nStartVRow);
enqueue(&g_qCol, _nStartVCol);
enqueue(&g_qDep, g_nDepth);
//printf("Start at (%d, %d).\n", _nStartVRow, _nStartVCol);
while (FALSE == isEmpty(&g_qRow) && FALSE == isEmpty(&g_qCol))
{
int nCurrVRow = dequeue(&g_qRow);
int nCurrVCol = dequeue(&g_qCol);
int nCurrDep = dequeue(&g_qDep);
if (g_uFinVRow == nCurrVRow && g_uFinVCol == nCurrVCol)
{
flag = 1;
if (nCurrDep < g_nMinDepth) g_nMinDepth = nCurrDep;
}
for (i = 0; i < DIRECTION; ++i)
{
int nNextVRow = nCurrVRow + g_nDirMat[i][0];
int nNextVCol = nCurrVCol + g_nDirMat[i][1];
int nNextDep = nCurrDep + 1;
if (TRUE == g_nVisitMat[nNextVRow][nNextVCol]) continue;
if (FALSE == g_nAdjMat[nNextVRow][nNextVCol] &&
1 <= nNextVRow && nNextVRow <= g_uVRowCnt &&
1 <= nNextVCol && nNextVCol <= g_uVColCnt)
{
g_nVisitMat[nNextVRow][nNextVCol] = TRUE;
enqueue(&g_qRow, nNextVRow);
enqueue(&g_qCol, nNextVCol);
enqueue(&g_qDep, nNextDep);
printf("[%d]: (%d, %d) -> (%d, %d)\n", nNextDep, nCurrVRow, nCurrVCol, nNextVRow, nNextVCol);
g_nBlockMat[nNextVRow][nNextVCol] = g_uBlockCnt;
}
}
}
}<hide/>
10 9
000100110
101010001
010010000
001000000
010010011
001100000
001000101
101000010
010011001
001100100
-1
11 10
0001110000
0010100001
0011100000
0101111010
1000010001
0001000001
1001100111
1101000000
0000100001
0101001001
0001001001
22
Ex) 미로찾기
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 101,
DIRECTION = 4
};
typedef struct queue {
int nArray[MAX_COUNT];
size_t uCnt;
size_t uFront;
size_t uRear;
} queue_t;
void enqueue(queue_t* _pQueue, int _nData);
int isEmpty(queue_t* _pQueue);
int dequeue(queue_t* _pQueue);
int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT][MAX_COUNT] = {0,};
size_t g_uVRowCnt, g_uVColCnt, g_uVStartRow, g_uVStartCol, g_uVFinishRow, g_uVFinishCol;
int g_nDirMat[DIRECTION][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
queue_t g_qRow, g_qCol, g_qDep;
int flag = 0;
void BFS(int _nStartRow, int _nStartCol, int _nStartDep);
int main(void)
{
size_t i, j;
scanf("%zu %zu", &g_uVRowCnt, &g_uVColCnt);
for (i = 1; i <= g_uVRowCnt; ++i)
{
for (j = 1; j <= g_uVColCnt; ++j)
{
scanf(" %c", &g_nAdjMat[i][j]);
if ('S' == g_nAdjMat[i][j])
{
g_uVStartRow = i;
g_uVStartCol = j;
}
if ('G' == g_nAdjMat[i][j])
{
g_uVFinishRow = i;
g_uVFinishCol = j;
}
}
}
BFS(g_uVStartRow, g_uVStartCol, 0);
if (0 == flag) printf("-1");
/*
printf("\n%zu %zu\n", g_uVRowCnt, g_uVColCnt);
for (i = 1; i <= g_uVRowCnt; ++i)
{
for (j = 1; j <= g_uVColCnt; ++j)
{
printf("%c", g_nAdjMat[i][j]);
}
printf("\n");
}
*/
return 0;
}
void enqueue(queue_t* _pQueue, int _nData)
{
assert(_pQueue->uCnt < MAX_COUNT);
_pQueue->nArray[_pQueue->uRear] = _nData;
_pQueue->uRear = (_pQueue->uRear + 1) % MAX_COUNT;
++_pQueue->uCnt;
}
int isEmpty(queue_t* _pQueue)
{
if (0 == _pQueue->uCnt) return TRUE;
return FALSE;
}
int dequeue(queue_t* _pQueue)
{
int ret;
assert(FALSE == isEmpty(_pQueue));
ret = _pQueue->nArray[_pQueue->uFront];
_pQueue->uFront = (_pQueue->uFront + 1) % MAX_COUNT;
--_pQueue->uCnt;
return ret;
}
void BFS(int _nStartRow, int _nStartCol, int _nStartDep)
{
int i, j;
g_nVisitMat[_nStartRow][_nStartCol] = TRUE;
enqueue(&g_qRow, _nStartRow);
enqueue(&g_qCol , _nStartCol);
enqueue(&g_qDep , _nStartDep);
while (FALSE == isEmpty(&g_qRow) && FALSE == isEmpty(&g_qCol) && FALSE == isEmpty(&g_qDep))
{
int nVCurrRow = dequeue(&g_qRow);
int nVCurrCol = dequeue(&g_qCol);
int nVCurrDep = dequeue(&g_qDep);
for (i = 0; i < DIRECTION; ++i)
{
int nVNextRow = nVCurrRow + g_nDirMat[i][0];
int nVNextCol = nVCurrCol + g_nDirMat[i][1];
int nVNextDep = nVCurrDep + 1;
if (g_uVFinishRow == nVNextRow && g_uVFinishCol == nVNextCol)
{
flag = 1;
printf("%d", nVNextDep);
return;
}
if (TRUE == g_nVisitMat[nVNextRow][nVNextCol]) continue;
if (('.' == g_nAdjMat[nVNextRow][nVNextCol] || 'S' == g_nAdjMat[nVNextRow][nVNextCol]) &&
1 <= nVNextRow && nVNextRow <= g_uVRowCnt &&
1 <= nVNextCol && nVNextCol <= g_uVColCnt)
{
g_nVisitMat[nVNextRow][nVNextCol] = TRUE;
enqueue(&g_qRow, nVNextRow);
enqueue(&g_qCol, nVNextCol);
enqueue(&g_qDep, nVNextDep);
printf("[%d]: (%d, %d) -> (%d, %d)\n", nVNextDep, nVCurrRow, nVCurrCol, nVNextRow, nVNextCol);
}
}
}
}<hide/>
// TestCase1
5 5
#S###
#...#
#.#.#
#....
###G#
// Expected
6
Ex) 체스 말 이동
- 테스트 케이스는 모두 맞음.
그러나, Segmentation Fault가 뜸.
- Segmentation Fault란, 두 가지 이유로 발생함.
첫째, 허용되지 않은 메모리에 접근(ex. const char*의 수정, nullptr 참조, etc...)
둘째, 허용되지 않은 방법으로 메모리에 접근(나중에 찾아보자.)
- 가장 유력한 부분은, 배열 첨자 연산자에 -2만큼 들어갈 수도 있는 부분.
- 그래서 범위 확인 부분을 우선적으로 검사하게끔,
중첩 if문을 사용함.
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
enum
{
FALSE = 0,
TRUE = 1,
MAX_COUNT = 10001,
DIRECTION = 8
};
typedef struct queue
{
int nArray[MAX_COUNT];
size_t uCnt;
size_t uFront;
size_t uRear;
} queue_t;
void enqueue(queue_t* _pQueue, int _nData);
int isEmpty(queue_t* _pQueue);
int dequeue(queue_t* _pQueue);
int g_nAdjMat[MAX_COUNT][MAX_COUNT] = { 0, };
int g_nVisitMat[MAX_COUNT][MAX_COUNT] = { 0, };
size_t g_uVCnt, g_uVStartRow, g_uVStartCol, g_uVFinishRow, g_uVFinishCol;
int g_nDirMat[DIRECTION][2] = { {-1, -2}, {-2, -1}, {-2, 1}, {-1, 2},
{1, -2}, {2, -1}, {2, 1}, {1, 2}
};
queue_t g_qRow, g_qCol, g_qDep;
void BFS(int _nVStartRow, int _nVStartCol, int _nStartDep);
int main(void)
{
size_t i, j;
scanf("%zu %zu %zu %zu %zu", &g_uVCnt, &g_uVStartRow, &g_uVStartCol, &g_uVFinishRow, &g_uVFinishCol);
BFS(g_uVStartRow, g_uVStartCol, 0);
return 0;
}
void enqueue(queue_t* _pQueue, int _nData)
{
assert(_pQueue->uCnt < MAX_COUNT);
_pQueue->nArray[_pQueue->uRear] = _nData;
_pQueue->uRear = (_pQueue->uRear + 1) % MAX_COUNT;
++_pQueue->uCnt;
}
int isEmpty(queue_t* _pQueue)
{
if (0 == _pQueue->uCnt) return TRUE;
return FALSE;
}
int dequeue(queue_t* _pQueue)
{
int ret;
assert(FALSE == isEmpty(_pQueue));
ret = _pQueue->nArray[_pQueue->uFront];
_pQueue->uFront = (_pQueue->uFront + 1) % MAX_COUNT;
--_pQueue->uCnt;
return ret;
}
void BFS(int _nVStartRow, int _nVStartCol, int _nStartDep)
{
size_t i;
if (g_uVFinishRow == _nVStartRow && g_uVFinishCol == _nVStartCol)
{
printf("0");
return;
}
g_nVisitMat[_nVStartRow][_nVStartCol] = TRUE;
enqueue(&g_qRow, _nVStartRow);
enqueue(&g_qCol, _nVStartCol);
enqueue(&g_qDep, _nStartDep);
while (FALSE == isEmpty(&g_qRow) && FALSE == isEmpty(&g_qCol))
{
int nVCurrRow = dequeue(&g_qRow);
int nVCurrCol = dequeue(&g_qCol);
int nCurrDep = dequeue(&g_qDep);
for (i = 0; i < DIRECTION; ++i)
{
int nVNextRow = nVCurrRow + g_nDirMat[i][0];
int nVNextCol = nVCurrCol + g_nDirMat[i][1];
int nNextDep = nCurrDep + 1;
if (g_uVFinishRow == nVNextRow && g_uVFinishCol == nVNextCol)
{
printf("%d", nNextDep);
return;
}
// if (TRUE == g_nVisitMat[nVNextRow][nVNextCol]) continue;
if (1 <= nVNextRow && nVNextRow <= g_uVCnt &&
1 <= nVNextCol && nVNextCol <= g_uVCnt)
{
if (FALSE == g_nVisitMat[nVNextRow][nVNextCol])
{
g_nVisitMat[nVNextRow][nVNextCol] = TRUE;
enqueue(&g_qRow, nVNextRow);
enqueue(&g_qCol, nVNextCol);
enqueue(&g_qDep, nNextDep);
// printf("[%d]: (%d, %d) -> (%d, %d)\n", nNextDep, nVCurrRow, nVCurrCol, nVNextRow, nVNextCol);
}
}
}
}
}<hide/>
// TestCase
8
1 1
2 2
// Expected
4
// TestCase
8
0 0
7 0
// Expected
5
// TestCase
100
0 0
30 50
// Expected
28
// TestCase
10
1 1
1 1
// Expected
0
Ex) 토마토
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 1001,
DIRECTION = 4
};
typedef struct queue {
int nArray[MAX_COUNT];
size_t uCnt;
size_t uFront;
size_t uRear;
} queue_t;
void enqueue(queue_t* _pQueue, int _nData);
int isEmpty(queue_t* _pQueue);
int dequeue(queue_t* _pQueue);
int g_nAdjMat[MAX_COUNT][MAX_COUNT] = { 0, };
int g_nVisitMat[MAX_COUNT][MAX_COUNT] = { 0, };
size_t g_uVRowCnt, g_uVColCnt;
int g_nDirMat[DIRECTION][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
queue_t g_qRow, g_qCol, g_qDep;
int g_nDay;
void BFS(void);
int main(void)
{
size_t i, j;
scanf("%zu %zu", &g_uVColCnt, &g_uVRowCnt);
for (i = 1; i <= g_uVRowCnt; ++i)
{
for (j = 1; j <= g_uVColCnt; ++j)
{
scanf("%d", &g_nAdjMat[i][j]);
if (1 == g_nAdjMat[i][j])
{
g_nVisitMat[i][j] = 1;
enqueue(&g_qRow, i);
enqueue(&g_qCol, j);
enqueue(&g_qDep, 1);
}
}
}
BFS();
for (i = 1; i <= g_uVRowCnt; ++i)
{
for (j = 1; j <= g_uVColCnt; ++j)
{
if (0 == g_nVisitMat[i][j] && 0 == g_nAdjMat[i][j])
{
printf("-1");
return 0;
}
}
}
printf("%d", g_nDay - 1);
return 0;
}
void enqueue(queue_t* _pQueue, int _nData)
{
assert(_pQueue->uCnt < MAX_COUNT);
_pQueue->nArray[_pQueue->uRear] = _nData;
_pQueue->uRear = (_pQueue->uRear + 1) % MAX_COUNT;
++_pQueue->uCnt;
}
int isEmpty(queue_t* _pQueue)
{
if (0 == _pQueue->uCnt) return TRUE;
return FALSE;
}
int dequeue(queue_t* _pQueue)
{
int ret;
assert(FALSE == isEmpty(_pQueue));
ret = _pQueue->nArray[_pQueue->uFront];
_pQueue->uFront = (_pQueue->uFront + 1) % MAX_COUNT;
--_pQueue->uCnt;
return ret;
}
void BFS(void)
{
size_t i, j;
while (FALSE == isEmpty(&g_qRow) && FALSE == isEmpty(&g_qCol))
{
int nVCurrRow = dequeue(&g_qRow);
int nVCurrCol = dequeue(&g_qCol);
int nCurrDep = dequeue(&g_qDep);
for (i = 0; i < DIRECTION; ++i)
{
int nVNextRow = nVCurrRow + g_nDirMat[i][0];
int nVNextCol = nVCurrCol + g_nDirMat[i][1];
int nNextDep = nCurrDep + 1;
if (1 == g_nVisitMat[nVNextRow][nVNextCol])
{
continue;
}
if (0 == g_nAdjMat[nVNextRow][nVNextCol] &&
1 <= nVNextRow && nVNextRow <= g_uVRowCnt &&
1 <= nVNextCol && nVNextCol <= g_uVColCnt)
{
g_nVisitMat[nVNextRow][nVNextCol] = TRUE;
enqueue(&g_qRow, nVNextRow);
enqueue(&g_qCol, nVNextCol);
enqueue(&g_qDep, nNextDep);
}
}
/*
printf("\n\t%d\n", nCurrDep - 1);
for (i = 1; i <= g_uVRowCnt; ++i)
{
for (j = 1; j <= g_uVColCnt; ++j)
{
printf("%d ", g_nVisitMat[i][j]);
}
printf("\n");
}
*/
g_nDay = nCurrDep;
}
}<hide/>
// TestCase
6 4
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 1
// Expected
8
// TestCase
22 22
1 0 1 -1 0 1 -1 -1 0 1 1 1 0 0 -1 0 0 1 0 1 0 1
1 1 0 1 0 0 0 -1 0 0 1 0 -1 1 0 1 0 -1 1 1 0 -1
0 0 0 0 1 -1 0 1 0 1 0 1 0 1 0 0 -1 1 0 0 0 0
1 0 1 -1 0 1 0 0 0 1 -1 0 1 1 0 0 -1 0 -1 0 1 1
-1 0 0 0 0 -1 1 -1 1 0 0 1 -1 0 1 -1 0 0 0 1 1 0
1 -1 0 1 0 0 1 -1 -1 0 1 -1 1 0 1 1 1 1 1 1 0 1
0 0 1 0 1 1 -1 1 0 -1 -1 0 -1 -1 1 0 1 0 0 0 1 1
-1 -1 0 0 1 1 0 1 0 1 0 0 0 0 0 0 1 -1 1 0 1 0
0 0 -1 0 -1 1 1 0 -1 0 0 -1 -1 -1 0 -1 0 -1 -1 0 0 -1
-1 0 -1 0 1 1 -1 0 0 1 0 1 -1 0 1 1 0 1 1 1 0 0
0 0 1 -1 1 1 1 0 0 1 -1 -1 -1 0 1 0 -1 1 0 0 -1 -1
-1 -1 0 1 -1 0 1 0 0 0 1 1 -1 1 0 0 1 0 -1 -1 1 1
0 -1 0 0 1 0 1 -1 -1 1 -1 0 1 -1 -1 1 1 0 0 1 0 -1
0 0 -1 0 0 1 0 1 0 1 1 0 1 1 1 0 1 0 1 0 1 0
0 1 0 0 0 -1 0 0 0 1 -1 1 0 1 -1 0 1 0 -1 1 -1 0
0 1 0 0 0 1 1 1 -1 -1 0 1 1 0 -1 1 -1 0 0 0 -1 1
1 1 1 0 0 0 1 1 -1 1 0 0 0 0 -1 1 0 0 1 0 0 0
-1 1 0 1 0 0 0 1 -1 1 0 1 -1 -1 0 -1 0 1 0 -1 1 -1
0 0 1 0 -1 1 -1 0 1 0 1 0 0 0 0 -1 -1 0 -1 -1 0 -1
0 1 1 1 0 1 0 0 1 1 -1 1 -1 0 1 1 1 -1 0 -1 0 -1
1 -1 0 -1 -1 0 -1 0 1 -1 0 -1 -1 0 1 0 1 0 0 -1 0 1
-1 0 1 0 0 1 1 0 1 0 0 0 -1 0 0 0 0 0 0 0 0 1
// Expected
4
// TestCase
6 3
1 -1 0 0 0 0
-1 0 -1 0 0 0
0 -1 0 1 0 0
// Expected
-1
Ex) 2색 칠하기
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
enum
{
FALSE = 0,
TRUE = 1,
MAX_COUNT = 1001,
DIRECTION = 2
};
typedef struct queue
{
int nArray[MAX_COUNT];
size_t uCnt;
size_t uFront;
size_t uRear;
} queue_t;
void enqueue(queue_t* _pQueue, int _nData);
int isEmpty(queue_t* _pQueue);
int dequeue(queue_t* _pQueue);
int g_nAdjMat[MAX_COUNT][MAX_COUNT] = { 0, };
int g_nVisitMat[MAX_COUNT] = { 0, };
size_t g_uVCnt, g_uECnt;
queue_t g_queue;
int g_nFlag = 0;
void BFS(int _nVStart);
int main(void)
{
size_t i, j, uV1, uV2;
scanf("%zu %zu", &g_uVCnt, &g_uECnt);
for (i = 1; i <= g_uECnt; ++i)
{
scanf("%zu %zu", &uV1, &uV2);
g_nAdjMat[uV1 + 1][uV2 + 1] = TRUE;
g_nAdjMat[uV2 + 1][uV1 + 1] = TRUE;
}
BFS(1);
for (i = 1; i <= g_uVCnt; ++i)
{
for (j = 1; j <= g_uVCnt; ++j)
{
if (1 == g_nAdjMat[i][j])
{
if (0 != g_nVisitMat[i] + g_nVisitMat[j])
{
printf("NOT BICOLORABLE");
return 0;
}
}
}
}
printf("BICOLORABLE");
return 0;
}
void enqueue(queue_t* _pQueue, int _nData)
{
assert(_pQueue->uCnt < MAX_COUNT);
_pQueue->nArray[_pQueue->uRear] = _nData;
_pQueue->uRear = (_pQueue->uRear + 1) % MAX_COUNT;
++_pQueue->uCnt;
}
int isEmpty(queue_t* _pQueue)
{
if (0 == _pQueue->uCnt) return TRUE;
return FALSE;
}
int dequeue(queue_t* _pQueue)
{
int ret;
assert(FALSE == isEmpty(_pQueue));
ret = _pQueue->nArray[_pQueue->uFront];
_pQueue->uFront = (_pQueue->uFront + 1) % MAX_COUNT;
--_pQueue->uCnt;
return ret;
}
void BFS(int _nVStart)
{
size_t i;
if (0 == g_nVisitMat[_nVStart]) g_nVisitMat[_nVStart] = 1;
enqueue(&g_queue, _nVStart);
while (FALSE == isEmpty(&g_queue))
{
int nVCurr = dequeue(&g_queue);
for (i = 1; i <= g_uVCnt; ++i)
{
if (0 == g_nVisitMat[i] && 1 == g_nAdjMat[nVCurr][i])
{
g_nVisitMat[i] = g_nVisitMat[nVCurr] * -1;
enqueue(&g_queue, i);
printf("(%d) -> (%d)\n", nVCurr, i);
}
}
}
}<hide/>
// TestCase
6
5
0 1
0 2
0 3
0 4
0 5
// Expected
BICOLORABLE
// TestCase
9
10
0 1
0 2
0 3
1 5
2 5
3 4
5 6
5 8
6 7
7 8
// Expected
BICOLORABLE
// TestCase
9 11
0 1
0 2
0 3
1 5
2 5
3 4
4 5
5 6
5 8
6 7
7 8
// Expected
NOT BICOLORABLE
Ex) 꽃길
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 101,
};
typedef struct queue {
int nArray[MAX_COUNT];
size_t uCnt;
size_t uFront;
size_t uRear;
} queue_t;
void enqueue(queue_t* _pQueue, int _nData);
int isEmpty(queue_t* _pQueue);
int dequeue(queue_t* _pQueue);
int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT] = {0,};
size_t g_uVCnt, g_uECnt;
queue_t g_queue;
void BFS(int _nVStart);
int main(void)
{
size_t i, uV1, uV2, uCnt = 0;
scanf("%zu %zu", &g_uVCnt, &g_uECnt);
for (i = 1; i <= g_uECnt; ++i)
{
scanf("%zu %zu", &uV1, &uV2);
g_nAdjMat[uV1][uV2] = TRUE;
g_nAdjMat[uV2][uV1] = TRUE;
}
for (i = 1; i <= g_uVCnt; ++i)
{
if (FALSE == g_nVisitMat[i])
{
BFS(i);
++uCnt;
}
}
printf("%zu", uCnt - 1);
return 0;
}
void enqueue(queue_t* _pQueue, int _nData)
{
assert(_pQueue->uCnt < MAX_COUNT);
_pQueue->nArray[_pQueue->uRear] = _nData;
_pQueue->uRear = (_pQueue->uRear + 1) % MAX_COUNT;
++_pQueue->uCnt;
}
int isEmpty(queue_t* _pQueue)
{
if (0 == _pQueue->uCnt) return TRUE;
return FALSE;
}
int dequeue(queue_t* _pQueue)
{
int ret;
assert(FALSE == isEmpty(_pQueue));
ret = _pQueue->nArray[_pQueue->uFront];
_pQueue->uFront = (_pQueue->uFront + 1) % MAX_COUNT;
--_pQueue->uCnt;
return ret;
}
void BFS(int _nVStart)
{
size_t i;
g_nVisitMat[_nVStart] = TRUE;
enqueue(&g_queue, _nVStart);
while (FALSE == isEmpty(&g_queue))
{
int nVCurr = dequeue(&g_queue);
for (i = 1; i <= g_uVCnt; ++i)
{
if (FALSE == g_nVisitMat[i] && TRUE == g_nAdjMat[nVCurr][i])
{
g_nVisitMat[i] = TRUE;
enqueue(&g_queue, i);
printf("%d -> %d\n", nVCurr, i);
}
}
}
}<hide/>
// TestCase
7
4
1 2
1 3
4 5
6 7
// Expected
2
Ex) 다리 만들기
- [21/12/10]
대륙 색칠 -> 타대륙 BFS 시행. 문제는 방문 처리.
결국 좌상단부터 BFS하기에, 우하단에 위치한 대륙의 끝부분은
이미 방문처리 되어있어서, 최단거리를 못찾게됨..
약 3일정도 도전하였으나, 추후에 BFS를 좀 더 연마하여 도전하기로 결정.
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 1001,
DIRECTION = 4
};
typedef struct queue {
int nArray[MAX_COUNT];
size_t uCnt;
size_t uFront;
size_t uRear;
} queue_t;
void enqueue(queue_t* _pQueue, int _nData);
int isEmpty(queue_t* _pQueue);
int dequeue(queue_t* _pQueue);
int g_nAdjMat[MAX_COUNT][MAX_COUNT] = { 0, };
int g_nVisitMat[MAX_COUNT][MAX_COUNT] = { 0, };
size_t g_uVCnt, g_uECnt, g_uCnt = 0;
int g_nDirMat[DIRECTION][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
queue_t g_qRow, g_qCol, g_qDep;
int g_nDepArr[MAX_COUNT] = { 0, }, g_nIdx = 0;
void BFSc(int _nVStartRow, int _nVStartCol);
void BFS(int _nVStartRow, int _nVStartCol, int _nStartCity);
int main(void)
{
size_t i, j, k, l, uV1, uV2;
int min = 2147483647;
scanf("%zu", &g_uVCnt);
for (i = 1; i <= g_uVCnt; ++i)
{
for (j = 1; j <= g_uVCnt; ++j)
{
scanf("%d", &g_nAdjMat[i][j]);
}
}
for (i = 1; i <= g_uVCnt; ++i)
{
for (j = 1; j <= g_uVCnt; ++j)
{
if (FALSE == g_nVisitMat[i][j] && TRUE == g_nAdjMat[i][j])
{
++g_uCnt;
BFSc(i, j); // Adjacency Matrix를 통해, Visit Matrix에 각 대륙 Labeling.
}
}
}
for (i = 1; i <= g_uVCnt; ++i)
{
for (j = 1; j <= g_uVCnt; ++j)
{
g_nAdjMat[i][j] = g_nVisitMat[i][j]; // 각 대륙의 Label을 Adjacency Matrix로 옮김.
g_nVisitMat[i][j] = FALSE; // Visit Matrix는 다시 초기화.
}
}
/*
printf("\n");
for (i = 1; i <= g_uVCnt; ++i)
{
for (j = 1; j <= g_uVCnt; ++j)
{
printf("%d ", g_nAdjMat[i][j]);
}
printf("\n");
}
*/
for (i = 1; i <= g_uVCnt; ++i)
{
for (j = 1; j <= g_uVCnt; ++j)
{
if (FALSE != g_nAdjMat[i][j] && FALSE == g_nVisitMat[i][j])
{
BFS(i, j, g_nAdjMat[i][j]); // 대륙 시작. 타 대륙으로 BFS.
}
}
}
for (i = 0; i < g_nIdx; ++i)
{
if (g_nDepArr[i] < min) min = g_nDepArr[i];
}
printf("%d", min);
return 0;
}
void enqueue(queue_t* _pQueue, int _nData)
{
assert(_pQueue->uCnt < MAX_COUNT);
_pQueue->nArray[_pQueue->uRear] = _nData;
_pQueue->uRear = (_pQueue->uRear + 1) % MAX_COUNT;
++_pQueue->uCnt;
}
int isEmpty(queue_t* _pQueue)
{
if (0 == _pQueue->uCnt) return TRUE;
return FALSE;
}
int dequeue(queue_t* _pQueue)
{
int ret;
assert(FALSE == isEmpty(_pQueue));
ret = _pQueue->nArray[_pQueue->uFront];
_pQueue->uFront = (_pQueue->uFront + 1) % MAX_COUNT;
--_pQueue->uCnt;
return ret;
}
void BFSc(int _nVStartRow, int _nVStartCol)
{
size_t i, j;
g_nVisitMat[_nVStartRow][_nVStartCol] = g_uCnt;
enqueue(&g_qRow, _nVStartRow);
enqueue(&g_qCol, _nVStartCol);
while (FALSE == isEmpty(&g_qRow) && FALSE == isEmpty(&g_qCol))
{
int nVCurrRow = dequeue(&g_qRow);
int nVCurrCol = dequeue(&g_qCol);
for (i = 0; i < DIRECTION; ++i)
{
int nVNextRow = nVCurrRow + g_nDirMat[i][0];
int nVNextCol = nVCurrCol + g_nDirMat[i][1];
if (FALSE != g_nVisitMat[nVNextRow][nVNextCol]) continue;
if (TRUE == g_nAdjMat[nVNextRow][nVNextCol] &&
1 <= nVNextRow && nVNextRow <= g_uVCnt &&
1 <= nVNextCol && nVNextCol <= g_uVCnt)
{
g_nVisitMat[nVNextRow][nVNextCol] = g_uCnt;
enqueue(&g_qRow, nVNextRow);
enqueue(&g_qCol, nVNextCol);
}
}
}
}
void BFS(int _nVStartRow, int _nVStartCol, int _nStartCity)
{
size_t i, j;
int nStartDep = 0;
g_nVisitMat[_nVStartRow][_nVStartCol] = TRUE;
enqueue(&g_qRow, _nVStartRow);
enqueue(&g_qCol, _nVStartCol);
enqueue(&g_qDep, nStartDep);
while (FALSE == isEmpty(&g_qRow) && FALSE == isEmpty(&g_qCol))
{
int nVCurrRow = dequeue(&g_qRow);
int nVCurrCol = dequeue(&g_qCol);
int nCurrDep = dequeue(&g_qDep);
for (i = 0; i < DIRECTION; ++i)
{
int nVNextRow = nVCurrRow + g_nDirMat[i][0];
int nVNextCol = nVCurrCol + g_nDirMat[i][1];
int nNextDep = nCurrDep + 1;
if (1 <= nVNextRow && nVNextRow <= g_uVCnt &&
1 <= nVNextCol && nVNextCol <= g_uVCnt)
{
if (FALSE == g_nVisitMat[nVNextRow][nVNextCol] && 0 == g_nAdjMat[nVNextRow][nVNextCol]) // 만약 바다라면, 더 탐색.
{
g_nVisitMat[nVNextRow][nVNextCol] = TRUE;
enqueue(&g_qRow, nVNextRow);
enqueue(&g_qCol, nVNextCol);
enqueue(&g_qDep, nNextDep);
// printf("[%d]: (%d, %d) -> (%d, %d)\n", nNextDep, nVCurrRow, nVCurrCol, nVNextRow, nVNextCol);
}
else if (_nStartCity != g_nAdjMat[nVNextRow][nVNextCol] && 0 != g_nAdjMat[nVNextRow][nVNextCol])
{ // 바다는 아니고, 출발 대륙과 다르다면 거리 기록.
g_nDepArr[g_nIdx++] = nNextDep - 1;
}
}
}
}
}<hide/>
// TestCase
10
1 1 1 0 0 0 0 1 1 1
1 1 1 1 0 0 0 0 1 1
1 0 1 1 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0 1
0 0 0 1 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 0 0
0 0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0
// Expected
3
// TestCase
36
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
// Expected
4
// TestCase
29
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
// Expected
8
Ex) 소들의 코딩 대회
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 7501,
};
typedef struct queue {
int nArray[MAX_COUNT];
size_t uCnt;
size_t uFront;
size_t uRear;
} queue_t;
void enqueue(queue_t* _pQueue, int _nData);
int isEmpty(queue_t* _pQueue);
int dequeue(queue_t* _pQueue);
int g_nAdjMat[MAX_COUNT][MAX_COUNT] = {0,};
int g_nVisitMat[MAX_COUNT] = {0,};
size_t g_uVCnt = 0, g_uECnt = 0, g_uWinCnt = 0, g_uLoseCnt = 0;
queue_t g_queue;
size_t g_uUpDownCntArray[MAX_COUNT][2];
void BFS_Up(int _nVStart);
void BFS_Down(int _nVStart);
int main(void)
{
size_t i, j, uV1, uV2, cnt = 0;
scanf("%zu %zu", &g_uVCnt, &g_uECnt);
for (i = 1; i <= g_uECnt; ++i)
{
scanf("%zu %zu", &uV1, &uV2);
g_nAdjMat[uV1][uV2] = TRUE;
}
for (i = 1; i <= g_uVCnt; ++i)
{
if (FALSE == g_nVisitMat[i])
{
BFS_Up(i);
}
for (j = 1; j <= g_uVCnt; ++j)
{
g_nVisitMat[j] = FALSE;
}
}
for (i = 1; i <= g_uVCnt; ++i)
{
if (FALSE == g_nVisitMat[i])
{
BFS_Down(i);
}
for (j = 1; j <= g_uVCnt; ++j)
{
g_nVisitMat[j] = FALSE;
}
}
for (i = 1; i <= g_uVCnt; ++i)
{
if (g_uVCnt - 1 == g_uUpDownCntArray[i][0] + g_uUpDownCntArray[i][1])
{
++cnt;
}
}
printf("%zu", cnt);
return 0;
}
void enqueue(queue_t* _pQueue, int _nData)
{
assert(_pQueue->uCnt < MAX_COUNT);
_pQueue->nArray[_pQueue->uRear] = _nData;
_pQueue->uRear = (_pQueue->uRear + 1) % MAX_COUNT;
++_pQueue->uCnt;
}
int isEmpty(queue_t* _pQueue)
{
if (0 == _pQueue->uCnt) return TRUE;
return FALSE;
}
int dequeue(queue_t* _pQueue)
{
int ret;
assert(FALSE == isEmpty(_pQueue));
ret = _pQueue->nArray[_pQueue->uFront];
_pQueue->uFront = (_pQueue->uFront + 1) % MAX_COUNT;
--_pQueue->uCnt;
return ret;
}
void BFS_Up(int _nVStart)
{
size_t i;
g_nVisitMat[_nVStart] = TRUE;
enqueue(&g_queue, _nVStart);
while (FALSE == isEmpty(&g_queue))
{
int nVCurr = dequeue(&g_queue);
for (i = 1; i <= g_uVCnt; ++i)
{
if (FALSE == g_nVisitMat[i] && TRUE == g_nAdjMat[i][nVCurr])
{ // nVCurr한테 이기는 소들로 이동.
g_nVisitMat[i] = TRUE;
enqueue(&g_queue, i);
++g_uUpDownCntArray[_nVStart][0];
}
}
}
}
void BFS_Down(int _nVStart)
{
size_t i;
g_nVisitMat[_nVStart] = TRUE;
enqueue(&g_queue, _nVStart);
while (FALSE == isEmpty(&g_queue))
{
int nVCurr = dequeue(&g_queue);
for (i = 1; i <= g_uVCnt; ++i)
{
if (FALSE == g_nVisitMat[i] && TRUE == g_nAdjMat[nVCurr][i])
{ // nVCurr한테 지는 소들로 이동.
g_nVisitMat[i] = TRUE;
enqueue(&g_queue, i);
++g_uUpDownCntArray[_nVStart][1];
}
}
}
}<hide/>
// TestCase
5 5
4 3
4 2
3 2
1 2
2 5
// Expected
2
Ex) 물통
<hide/>
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
enum {
FALSE = 0,
TRUE = 1,
MAX_COUNT = 201,
};
typedef struct queue {
int nArray[MAX_COUNT];
size_t uCnt;
size_t uFront;
size_t uRear;
} queue_t;
void enqueue(queue_t* _pQueue, int _nData);
int isEmpty(queue_t* _pQueue);
int dequeue(queue_t* _pQueue);
int g_nVisitMat[MAX_COUNT][MAX_COUNT][MAX_COUNT] = {0,};
size_t g_uASize, g_uBSize, g_uCSize, g_uIdx = 0;
queue_t g_qA, g_qC, g_qB;
int g_nStateMat[MAX_COUNT] = {0,};
void BFS(int _nStartA, int _nStartB, int _nStartC);
void move(int _nSrc, int _nDes, int _nKeep, size_t _uDesSize);
int compare(const void* a, const void* b) { return *(int*)a > *(int*)b; }
int main(void)
{
size_t i;
scanf("%zu %zu %zu", &g_uASize, &g_uBSize, &g_uCSize);
BFS(0, 0, (int)g_uCSize);
qsort(g_nStateMat, (int)g_uIdx, sizeof(g_nStateMat[0]), compare);
for (i = 0; i < g_uIdx; ++i)
{
printf("%d ", g_nStateMat[i]);
}
return 0;
}
void enqueue(queue_t* _pQueue, int _nData)
{
assert(_pQueue->uCnt < MAX_COUNT);
_pQueue->nArray[_pQueue->uRear] = _nData;
_pQueue->uRear = (_pQueue->uRear + 1) % MAX_COUNT;
++_pQueue->uCnt;
}
int isEmpty(queue_t* _pQueue)
{
if (0 == _pQueue->uCnt) return TRUE;
return FALSE;
}
int dequeue(queue_t* _pQueue)
{
int ret;
assert(FALSE == isEmpty(_pQueue));
ret = _pQueue->nArray[_pQueue->uFront];
_pQueue->uFront = (_pQueue->uFront + 1) % MAX_COUNT;
--_pQueue->uCnt;
return ret;
}
void BFS(int _nStartA, int _nStartB, int _nStartC)
{
enqueue(&g_qA, _nStartA);
enqueue(&g_qB, _nStartB);
enqueue(&g_qC, _nStartC);
while (FALSE == isEmpty(&g_qA))
{
int nCurrA = dequeue(&g_qA);
int nCurrB = dequeue(&g_qB);
int nCurrC = dequeue(&g_qC);
if (TRUE == g_nVisitMat[nCurrA][nCurrB][nCurrC]) continue;
g_nVisitMat[nCurrA][nCurrB][nCurrC] = TRUE;
// printf("%d %d %d\n", nCurrA, nCurrB, nCurrC);
if (0 == nCurrA)
{
g_nStateMat[g_uIdx++] = nCurrC;
}
// A -> B
if (nCurrA + nCurrB <= g_uBSize)
{
enqueue(&g_qA, 0);
enqueue(&g_qB, nCurrA + nCurrB);
enqueue(&g_qC, nCurrC);
}
else
{
enqueue(&g_qA, nCurrA - (g_uBSize - nCurrB));
enqueue(&g_qB, nCurrB + (g_uBSize - nCurrB));
enqueue(&g_qC, nCurrC);
}
// A -> C
if (nCurrA + nCurrC <= g_uCSize)
{
enqueue(&g_qA, 0);
enqueue(&g_qB, nCurrB);
enqueue(&g_qC, nCurrA + nCurrC);
}
else
{
enqueue(&g_qA, nCurrA - (g_uCSize - nCurrC));
enqueue(&g_qB, nCurrB);
enqueue(&g_qC, nCurrC + (g_uCSize - nCurrC));
}
// B -> A
if (nCurrB + nCurrA <= g_uASize)
{
enqueue(&g_qA, nCurrB + nCurrA);
enqueue(&g_qB, 0);
enqueue(&g_qC, nCurrC);
}
else
{
enqueue(&g_qA, nCurrA + (g_uASize - nCurrA));
enqueue(&g_qB, nCurrB - (g_uASize - nCurrA));
enqueue(&g_qC, nCurrC);
}
// B -> C
if (nCurrB + nCurrC <= g_uCSize)
{
enqueue(&g_qA, nCurrA);
enqueue(&g_qB, 0);
enqueue(&g_qC, nCurrB + nCurrC);
}
else
{
enqueue(&g_qA, nCurrA);
enqueue(&g_qB, nCurrB - (g_uCSize - nCurrC));
enqueue(&g_qC, nCurrC + (g_uCSize - nCurrC));
}
// C -> A
if (nCurrC + nCurrA <= g_uASize)
{
enqueue(&g_qA, nCurrC + nCurrA);
enqueue(&g_qB, nCurrB);
enqueue(&g_qC, 0);
}
else
{
enqueue(&g_qA, nCurrA + (g_uASize - nCurrA));
enqueue(&g_qB, nCurrB);
enqueue(&g_qC, nCurrC - (g_uASize - nCurrA));
}
// C -> B
if (nCurrC + nCurrB <= g_uBSize)
{
enqueue(&g_qA, nCurrA);
enqueue(&g_qB, nCurrC + nCurrB);
enqueue(&g_qC, 0);
}
else
{
enqueue(&g_qA, nCurrA);
enqueue(&g_qB, nCurrB + (g_uBSize - nCurrB));
enqueue(&g_qC, nCurrC - (g_uBSize - nCurrB));
}
}
}<hide/>
//TestCase
3 6 7
//Expected
1 3 4 6 7
//TestCase
8 9 10
//Expected
1 2 8 9 10