[백준 1260번/C언어] 미로 탐색, BFS로 풀이

백준 2178번 문제를 BFS(Breadth-First Search)를 활용하여 풀어보았습니다. 

백준 2178번: https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

 

 

문제 내용은 아래와 같습니다. 

 

 

 이 문제는 처음에 다른 방식으로 접근했다가 시간초과가 떠서 다시 힌트를 조금 참고해서 BFS를 활용해서 만들었습니다. BFS 구현이나 설명은 제 블로그 글 중 아래 글에서 참고하시면 됩니다. 

https://programming-diary-ina.tistory.com/30

[백준 1260번/C언어] DFS와 BFS, Queue로 풀이

 

 

 코드를 자세히 살펴보면, 크게 POINT 구조체와 2개의 전역변수, makeElem() 함수 그리고 main 함수 이렇게 총셰퍼드로 나눠볼 수 있습니다. 

 

 우선 POINT 구조체와 전역변수들에 대해서 먼저 언급하겠습니다. POINT 구조체는 x, y, 그리고 pre 변수를 가지고 있습니다. x와 y는 미로에서의 좌표값을 저장하기 위해 만든 변수이고, pre 변수는 현재 좌표값 직전에 방문한 칸까지 가는 데까지 지난 칸 수를 나타냅니다. pre를 저장해 두면 간단히 pre + 1로 현재 칸까지 오는 데의 값을 파악할 수 있기 때문에 이렇게 정보를 저장해 두었습니다. 그리고 전역 변수들을 하나씩 살펴보면, 우선 queue 배열은 앞서 선언한 POINT 구조체 배열이고, BFS를 구현하기 위해 사용될 큐 자료구조 배열입니다. maze는 입력으로 주어질 미로 정보를 저장할 배열입니다. 

 

 두 개의 함수 중에서는 main 함수를 먼저 보겠습니다. 우선 미로의 크기에 해당하는 입력 값인 N과 M을 변수에 저장하고, 열의 개수에 해당하는 N만큼 반복하며 M만큼의 길이의 문자열을 maze 배열에 입력받습니다. 여기서 주의할 점이 maze 배열은 int 배열로 선언하고 N x M만큼 반복하면서 int값으로 받게 되면 오류가 발생합니다. 문제에서 제시된대로 숫자들이 다 붙어서 입력되기 때문에 입력받은 0과 1의 조합을 하나의 정수로 인식하기 때문입니다. 이는 overflow까지도 발생시킬 수 있고, overflow가 발생하지 않는다고 해도 원하는 대로 실행되기 않기 때문에 주의해야 합니다. 이후 queue의 첫 번째 요소로 0. 0 좌표값과 함께 pre가 0인 구조체를 넣어주고, BFS 재귀함수를 시작합니다. 그 리턴값을 바로 출력하면 되기 때문에 따로 변수를 두지 않고 print 하면 됩니다. 

 

 다음으로 BFS() 함수를 보면, 우선 head가 tail보다 크거나 같으면 0을 리턴하게 하는데, 왜냐하면 이후에 조건으로 좌표값이 도착점이라면 바로 해당 위치까지 지난 칸의 개수를 리턴하게 되어있기 때문입니다. 따라서 head가 tail보다 크거나 같다는 것은 적절한 위치에 도달하지 못하고 함수가 종료되는 것을 의미합니다. 문제에서 이미 이런 경우가 없다고 제시했기 때문에 처리하지 않아도 문제는 없지만 혹시 모를 무한 반복을 막기 위해 설정해뒀습니다.

 그리고는 조건을 확인하고 조건에 맞으면 인접 노드를 queue에 넣고 다음 요소에 대해 순회하는 과정을 반복하게 됩니다. 우선 cur변수에 현재 노드를 넣어주고, 현재 노드가 도착점인지 확인하고 맞다면 이전 노드까지 지난 칸 수 + 1을 바로 리턴해줍니다.

 만약 도착점이 아니라면, 현재 노드를 지나갈 수 있는지 체크하고 지나갈 수 없다면 바로 BFS를 재실행해줍니다. 만약 지나갈 수 있다면 지난 칸수에 1을 더해준 후 인접 노드에 접근하게 됩니다. 그리고 현재 노드에 관한 maze 배열 값을 '0'으로 바꿔주는데, 이는 visited를 표시한다고 생각해주시면 됩니다. ('0' 값을 가진 위치는 지나갈 수 없다는 의미로 이미 사용되고 있으므로 굳이 다른 값보다는 '0' 값으로 visited를 표시하여 재방문을 막아주었습니다.) 그 이후, 접근할 인접 노드가 접근 가능한지(미로 범위를 벗어나지 않는지) 확인해 준 후 가능하다면 queue에 넣어주고 BFS를 재실행합니다. 

#include <stdio.h>

typedef struct POINT {
    int x;
    int y;
    int pre;
} point;

point queue[50000];
char maze[101][101];

point makeElem(int x, int y, int pre) {
    point elem;
    elem.x = x;
    elem.y = y;
    elem.pre = pre;
    return elem;
}

int BFS(int head, int tail, int N, int M) {
    if (head >= tail) return 0;
    
    point cur = queue[head++];
    if (cur.x == (N-1) && cur.y == (M-1)) return (cur.pre + 1);
    if (maze[cur.x][cur.y] == '1') {
        int res = cur.pre + 1;
        maze[cur.x][cur.y] = '0';
        if (cur.x > 0) 
            queue[tail++] = makeElem(cur.x - 1, cur.y, res);
        if (cur.y > 0)
            queue[tail++] = makeElem(cur.x, cur.y - 1, res);
        if ((cur.x + 1) < N)
            queue[tail++] = makeElem(cur.x + 1, cur.y, res);
        if ((cur.y + 1) < M)
            queue[tail++] = makeElem(cur.x, cur.y + 1, res);
    }
    return BFS(head, tail, N, M);
}

int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    
    for (int i = 0; i < N; i++) {
        scanf("%s", maze[i]);
    }
    
    queue[0] = makeElem(0, 0, 0);
    printf("%d", BFS(0, 1, N, M));
}