BOJ 2178번 : 미로탐색

미로에서 끝까지 연결되어있는 길을 찾아내는것은 DFS, BFS 모두 가능하지만, 최단 거리를 찾아낼때는 BFS를 사용해야 한다.

(DFS가 구현하기 편해서 그렇게 하다가 안되는걸 직접 알았기 때문에 알게 됬당....)

 

<Solution>

DFS로 이 문제를 풀기 힘든 이유는, 처음 선택하게 되는 길로 계속 탐색을 하기 때문이다.

이렇게 탐색을 할 경우에 선택한 길이 가장 최단경로 라는 보장이 없기 때문에 여러 복잡한 조건들을 달아야 하게 될것이다. (경험담..)

 

BFS로 풀면 쉬운 이유는 같은 계층이 즉 같은 거리가 되기 때문이다.

아래 지도를 예제로 들어보자.

지도

BFS를 (1,1)에서 시작하면, 네방면으로 같은 계층이므로 같기 때문에 인접한 부분의 거리는 아래와 같다.

이렇게 된다면, 거리가 멀어지더라도 같은 거리(계층)을 판단 할 수 있다. 이를 계속하면 아래와 같다.

이렇게 되면, 자연스럽게 최단거리를 알아낼 수 있다.

 

방문체크를 하는 배열을 이렇게 거리를 알아내는 배열로 사용할수가 있다.

 

<소스코드>

#include<iostream>
#include<string.h>
#include<queue>
 
using namespace std;
int chk[101][101] = { 0, }; // 경로에 따른 카운트 여기 포함.
int arr[101][101] = { 0, };
int n, m;
int temp_x, temp_y;
queue<int> qy;
queue<int> qx;
 
void bfs(int y, int x) {
 
    chk[y][x] = 1;
    qx.push(x);
    qy.push(y);
 
    while (!qx.empty()) {
        temp_x = qx.front();
        temp_y = qy.front();
        qx.pop();
        qy.pop();
 
        if (!chk[temp_y + 1][temp_x] && arr[temp_y + 1][temp_x]) { // 아래
            chk[temp_y + 1][temp_x] = chk[temp_y][temp_x] + 1;     // 계층(거리) 더해줌
            qx.push(temp_x);
            qy.push(temp_y+1);
        }
        if (!chk[temp_y][temp_x + 1] && arr[temp_y][temp_x + 1]) { // 오른
            chk[temp_y][temp_x + 1] = chk[temp_y][temp_x] + 1;
            qx.push(temp_x + 1);
            qy.push(temp_y);
        }
        if (!chk[temp_y - 1][temp_x] && arr[temp_y - 1][temp_x]) { // 위
            chk[temp_y - 1][temp_x] = chk[temp_y][temp_x] + 1;
            qx.push(temp_x);
            qy.push(temp_y - 1);
        }
        if (!chk[temp_y ][temp_x - 1] && arr[temp_y ][temp_x - 1]) { // 왼
            chk[temp_y ][temp_x - 1] = chk[temp_y][temp_x] + 1;
            qx.push(temp_x - 1);
            qy.push(temp_y );
        }
    }
}
 
void Solve() {
    cin >> n >> m;
    getchar();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++)
            arr[i][j] = getchar() - '0';
        getchar();
    }
    bfs(1, 1);
    cout << chk[n][m];
}
 
int main() {
        Solve();
}
 

 

<문제>

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

2178번: 미로 탐색