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

2178번: 미로 탐색

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

미로에서 (N, M)에 도달하는 최단 거리를 구하여라.

 

---

시간복잡도 어림하기

BFS 알고리즘

 가중치가 같은 최단거리 문제이므로 BFS알고리즘을  사용하여 해결할 수 있습니다. 이때, 모든 칸은 한 번씩만 방문하므로 시행 횟수는 N x M으로 최대 10,000 입니다. 이는 제한 시간 내에 문제를 해결하기 충분한 수치이므로 BFS를 사용하여 문제를 해결하겠습니다.

---

알고리즘 설계하기

BFS알고리즘의 구조는 다음과 같습니다.

1. queue에 시작 위치 push 및 시작 위치 방문처리
2. queue가 비어있지 않을 때까지 아래 동작 반복
3. queue에서 가장 앞 위치를 꺼내고, queue를 pop
4. 현재 위치에서 갈 수 있는 다음 위치를 탐색
5. 다음 위치가 이동할 수 있는 위치라면 queue에 push하고, 방문 처리
6. 반복

 

 이 문제의 시작 위치는 가장 왼쪽 위 좌표이고 이를 (0, 0)이라 하겠습니다. 그렇다면, 우리가 도달해야 하는 (N, M)좌표는 (N - 1, M - 1)이 됩니다.

 

 먼저 (0, 0)을 queue에 push하고 방문처리를 합니다. 이후 while 루프에 queue가 비어있지 않을 때까지라는 조건을 넣어 반복문을 실행합니다.

 

 queue의 가장 앞 원소는 front() 메서드를 통해 꺼냅니다. 이후 pop() 메서드를 실행하여 queue에서 현재 위치를 제거합니다.

 

 다음 위치 탐색은 방향 배열을 활용하여 쉽게 구현할 수 있습니다. 이 문제에서는 상하좌우 네 방향만 탐색하므로 다음과 같이 방향 배열을 구성할 수 있습니다.

 int dy[ ] = {-1, 0, 1, 0};
 int dx[ ] = {0, 1, 0, -1};
인덱스 순서대로 상, 우, 하, 좌를 의미

 

 이후 다음 위치 유효성 검사를 진행합니다. 다음 위치가 배열의 밖인지, 이미 방문한 위치인지, 벽인지 확인하는 단계입니다. if문으로 구현하면 됩니다.

 

 모든 유효성 검사를 통과했다면, 이동할 수 있는 위치이므로 queue에 push하고 방문처리를 진행합니다

 

 이를 바탕으로 코드를 구현해봅시다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

#include<iostream>
#include<queue>
#include<tuple>
using namespace std;

int n, m, a[104][104], visited[104][104];
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
queue<pair<int, int>> q;
int main(){
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++)
            scanf("%1d", &a[i][j]);
    }
    /*시작점 추가*/
    q.push({0, 0}); visited[0][0] = 1;
    int y, x;
    while(!q.empty()){
        tie(y, x) = q.front(); q.pop();
        for(int i = 0; i < 4; i++){
            int ny = y + dy[i];
            int nx = x + dx[i];
            /*유효성 검사*/
            if(ny < 0 || nx < 0 || ny >= n || nx >= m) continue;
            if(visited[ny][nx] || a[ny][nx] == 0) continue;
            /*다음 위치 방문*/
            visited[ny][nx] = visited[y][x] + 1;
            q.push({ny, nx});
        }
    }
    cout << visited[n - 1][m - 1];
    return 0;
}

 입력 부분을 보면 scanf("%1d", ...) 으로 받는 것을 볼 수 있습니다. 이렇게 %뒤에 1을 넣으면 숫자 한 개씩 입력을 받을 수 있습니다. 이 방법 대신 한 줄을 문자열로 받아 한 글자씩 배열에 저장해도 됩니다.

 

 이후 BFS 알고리즘은 설계단계의 내용을 그대로 구현한 것입니다. 여기서 visited[ny][nx] = visited[y][x] + 1로 방문처리를 해 최단거리를 갱신하는 부분에 주의해주세요.

---