[백준] 2178번 : 미로 탐색

문제

 

---

풀이

 

이런 미로가 있다고 하자. 설명을 편하게 하기 위해 사방이 뚫린 미로를 만들었다.

빨간색이 시작점이고 파란색이 도착점이다. 파란색까지의 최단 거리는 어떻게 될까?

 

시작점에서 바로 아래, 오른쪽에 있는 좌표까지의 최단거리는 2일 것이다.

 

그 다음엔 이렇게 되고, 계속 하다보면...

 

이렇게 최단거리를 찾았다.

 

지금 이 과정은 bfs로 한거나 다름없다.

왜냐하면 시작점(1, 1)에 대해 갈 수 있는 좌표((2, 1), (1, 2))를 큐에 넣었고

최단거리가 2인 좌표들을 순서대로 방문하며 갈 수 있는 좌표((3, 1), (2, 2), (1, 3))를 큐에 넣어

또다시 순서대로 해당 좌표들을 방문하며 진행했기 때문이다.

 

그럼 왜 dfs는 안될까?

그림을 통한 설명을 하기 전 간단하게 말하자면 dfs는 잘못된 길을 파고들 수 있기 때문이다.

 

이런 미로가 있다고 하자. 상하좌우 순서로 방문 가능성을 확인할 것이기 때문에

dfs는 (2, 1)의 방문이 가능한 것을 확인하자 마자 거기로 이동할 것이다. 그리고 (3, 1)로가고...(4, 1)로 가고...

 

근데 이런 질문을 할 수도 있다.

길을 잘못 들어갔다고 할지라도 언젠가 막힌 곳을 발견하고 되돌아 오지 않을까?

 

이 미로를 dfs로 방문해보겠다.

 

이정도만 해도 뭐가 문제인지 알 수 있을 것이다.

 

아무튼 그래서 bfs로 구현해보자

---

소스코드

 

#include <iostream>
#include <string>
#include <queue>
#include <utility>

using namespace std;

//범위 초과 때문에 상하좌우 한줄씩 추가
int matrix[102][102], N, M;
pair<int, int> dir[4] = {{-1, 0}, //상
                         {1, 0},  //하
                         {0, -1}, //좌
                         {0, 1}}; //우

void bfs(pair<int, int> start) { //큐로 구현
    queue<pair<int, int>> q;

    q.push(start);
    while (!q.empty()) { //큐에 들어있는 모든 원소에 대해 가능한 방향 체크
        int row = q.front().first;
        int col = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) { //상하좌우 체크
            int next_row = row + dir[i].first;
            int next_col = col + dir[i].second;
            if (matrix[next_row][next_col] == 1) {
                matrix[next_row][next_col] = matrix[row][col] + 1; //matrix[next_row][next_col]를 오기 위해 몇 번 거쳐야 하는가?
                q.push(make_pair(next_row, next_col));
            }
        }
    }
}

int main() {
    string tmp;

    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> tmp;
        for (int j = 1; j <= M; j++)
            matrix[i][j] = tmp[j - 1] - '0';
    }
    pair<int, int> start = {1, 1};
    bfs(start);
    cout << matrix[N][M];
}

전체 소스코드다.

 

//범위 초과 때문에 상하좌우 한줄씩 추가
int matrix[102][102], N, M;
pair<int, int> dir[4] = {{-1, 0},  //상
                         {1, 0},  //하
                         {0, -1}, //좌
                         {0, 1}}; //우

아무생각 없이 상하좌우를 접근하다가 인덱스 범위를 벗어날 수 있으니까 최대 입력보다 2씩 더한 2차원 배열과

상하좌우를 편하게 접근하기 위해 만든 pair형 배열이다.

 

    pair<int, int> start = {1, 1};
    bfs(start);

(1, 1)에서 출발한다고 했으니까 이곳을 시작점으로 하는 bfs 함수를 호출한다.

 

void bfs(pair<int, int> start) { //큐로 구현
    queue<pair<int, int>> q;

    q.push(start);
    while (!q.empty()) { //큐에 들어있는 모든 원소에 대해 가능한 방향 체크
        int row = q.front().first;
        int col = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) { //상하좌우 체크
            int next_row = row + dir[i].first;
            int next_col = col + dir[i].second;
            if (matrix[next_row][next_col] == 1) {
                matrix[next_row][next_col] = matrix[row][col] + 1; //matrix[next_row][next_col]를 오기 위해 몇 번 거쳐야 하는가?
                q.push(make_pair(next_row, next_col));
            }
        }
    }
}

bfs 함수이다.

 

        int row = q.front().first;
        int col = q.front().second;

여기서 현재 좌표를 저장한다.

 

        for (int i = 0; i < 4; i++) { //상하좌우 체크
            int next_row = row + dir[i].first;
            int next_col = col + dir[i].second;
            if (matrix[next_row][next_col] == 1) {
                matrix[next_row][next_col] = matrix[row][col] + 1; //matrix[next_row][next_col]를 오기 위해 몇 번 거쳐야 하는가?
                q.push(make_pair(next_row, next_col));
            }
        }

현재 좌표의 상하좌우 좌표를 확인하며 방문 가능 여부를 체크한다.

만약 방문한 적없는 좌표라면 현재좌표에 1을 더한 값으로 갱신해준다. 이 값이 해당 좌표까지의 최단거리이다.

그리고나서 이 새로운 좌표를 큐에 넣어준다.

 

문제에서 도착점으로 못가는 경우는 없다고 했기 때문에 마지막에 도착점의 값을 출력하면 된다.