본문 바로가기
C/자료구조와 알고리듬

Chapter 15. BFS

by GameStudy 2021. 12. 2.

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
저작자표시 비영리 변경금지

'C > 자료구조와 알고리듬' 카테고리의 다른 글

Chapter 16. Backtracking  (0) 2021.12.12
Chapter 14. DFS  (0) 2021.11.28
Chapter 13. 그래프(Graph)  (0) 2021.11.26
Chapter 12. 힙(Heap)  (0) 2021.11.25
Chapter 11. 이진 탐색 트리(Binary Search Tree)  (0) 2021.11.21

관련글

댓글

티스토리툴바