[백준 2178번][C] 미로 탐색 (BFS)

snupi.tistory.com/107

[C] 너비 우선 탐색(BFS; Breadth First Search) 개념 및 정리

---

출처 : https://www.acmicpc.net/problem/2178

이 문제 역시 기본적인 최단 경로 문제이다

최단 경로 알고리즘은 BFS의 가장 큰 장점이므로 이를 활용해보자

 

• adj 행렬(, 미로)의 크기 및 칸의 정보를 입력받는다
• 인접한 칸을 queue에 push 시킨다
• queue가 빌 때까지 pop 하며 인접한 칸의 정보를 push 시킨다 (BFS)

---

0. 전역변수 설정

#define MAX 102
int adj[MAX][MAX]; // 미로 칸 정보 행렬로써 입력
int distance[MAX][MAX]; // (1, 1) 에서부터의 거리
int data[2][MAX*MAX]; // (data[0][], data[1][]) 좌표의 값

 

1. 정보 입력 및 초기화

int N, M;
scanf("%d %d", &N, &M);
for(int i=1; i<=N; i++) {
    for(int j=1; j<=M; j++) {
        scanf("%1d", &adj[i][j]);

        // init
        if(adj[i][j] == 1)
            distance[i][j] = 0;
        else
            distance[i][j] = -1;
    }
}

 

2. queue 생성 및 (1, 1) 첫 좌표 설정

int here[2]; // N, M
int there[2]; // N, M

int front, rear;
front = -1; // front
rear = -1; // rear

distance[startN][startM] = 1;
data[0][++rear] = startN; // push
data[1][rear] = startM; // push

 

3. 상하좌우 인접한 칸의 정보 push (BFS)

while(front < rear) { // queue가 빌 때까지 반복한다
    here[0] = data[0][++front]; // pop
    here[1] = data[1][front]; // pop
    
    if(adj[here[0]-1][here[1]] == 1) { // 상
        there[0] = here[0]-1;
        there[1] = here[1];

        if(!distance[there[0]][there[1]]) { // visit 하지 않은 칸이라면
            distance[there[0]][there[1]] = distance[here[0]][here[1]] + 1; // here에 +1
            data[0][++rear] = there[0]; // push
            data[1][rear] = there[1]; // push
        }
    }
    if(adj[here[0]+1][here[1]] == 1) { // 하
        there[0] = here[0]+1;
        there[1] = here[1];

        if(!distance[there[0]][there[1]]) {
            distance[there[0]][there[1]] = distance[here[0]][here[1]] + 1;
            data[0][++rear] = there[0];
            data[1][rear] = there[1];
        }
    }
    if(adj[here[0]][here[1]-1] == 1) { // 좌
        there[0] = here[0];
        there[1] = here[1]-1;

        if(!distance[there[0]][there[1]]) {
            distance[there[0]][there[1]] = distance[here[0]][here[1]] + 1;
            data[0][++rear] = there[0];
            data[1][rear] = there[1];
        }
    }
    if(adj[here[0]][here[1]+1] == 1) { // 우
        there[0] = here[0];
        there[1] = here[1]+1;

        if(!distance[there[0]][there[1]]) {
            distance[there[0]][there[1]] = distance[here[0]][here[1]] + 1;
            data[0][++rear] = there[0];
            data[1][rear] = there[1];
        }
    }

    //인접행렬 구하기 (DFS for문과 if문 똑같다)
    /*for(int i=1; i<=N; i++) {
        if(adj[here][i]) {
            there = i;

            if(!distance[there]) {
                distance[there] = distance[here] + 1;
                parent[there] = here;
                q.data[++q.rear] = there; // push
            }
        }
    }*/
}

 

4. distance[N][M]을 출력한다