[백준 2178] 미로 탐색 [C]

백준 - 2178

---

풀이

(0, 0)부터 범위를 초과하지 않고, 이동할 수 있는 공간이고, 방문한적 없는 곳을 탐색하면 된다.

다음에 이동할 좌표 (tx, ty)를 구조체 q에 저장하고 front, rear을 이용해 탐색을 진행했다.

---

소스코드

#include <stdio.h>
#include <stdbool.h>
bool visited[100][100];
int graph[100][100], d[100][100];
int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};
typedef struct{
    int x, y;
}Queue;

void bfs(int N, int M){
    d[0][0] = visited[0][0] = 1;
    Queue q[N*M];
    q[0].x = q[0].y = 0;
    int x, y, front = 0, rear = 1;
    while (front != rear){
        x = q[front].x;
        y = q[front].y;
        front++;
        for (int i = 0; i < 4; i++){
            int tx = x+dx[i], ty = y+dy[i];
            if (tx >= 0 && ty >= 0 && tx < N && ty < M)
                if (!visited[tx][ty] && graph[tx][ty]){
                    visited[tx][ty] = 1;
                    q[rear].x = tx;
                    q[rear++].y = ty;
                    d[tx][ty] = d[x][y] + 1;
                }			
        }
    }
}
int main(){
    int N, M;
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            scanf("%1d", &graph[i][j]);
    bfs(N, M);
    printf("%d", d[N-1][M-1]);
}

---

출처

2178번: 미로 탐색