[PS] 백준 2178 미로탐색

이번에는 백준 2178번 미로탐색 문제를 풀어보았습니다.

이 문제는 N x M 크기의 미로에서 (1, 1)에서 (N, M)까지 이동할 때, 지나야 하는 최소 칸 수를 구하는 문제입니다.

각 칸은 이동 가능 여부만 다르고, 이동 자체의 비용은 모두 같기 때문에 최소 경로 문제를 BFS로 해결하는 대표적인 문제였습니다.

---

문제 설명

미로는 N x M 배열로 주어지고,

• 1은 이동할 수 있는 칸
• 0은 이동할 수 없는 칸

을 의미합니다.

시작점은 (1, 1), 도착점은 (N, M)이며,

상하좌우 인접한 칸으로만 이동할 수 있습니다.

이때 도착점까지 이동할 때 지나야 하는 최소 칸 수를 출력하면 됩니다.

시작 위치와 도착 위치도 칸 수에 포함됩니다.

---

풀이 아이디어

이 문제는 한 칸 이동할 때마다 비용이 모두 같습니다.

즉, 어떤 칸에서 다른 칸으로 이동할 때의 가중치가 전부 동일합니다.

이런 경우에는 BFS를 사용하면 시작점에서 각 칸까지의 최소 이동 횟수를 자연스럽게 구할 수 있습니다.

그래서 이 문제에서는

• 미로 정보는 inp_map
• 방문 여부와 거리 정보는 visited

에 저장하고,

BFS를 돌면서 방문하는 칸마다 이전 칸의 값에 1을 더해 최소 칸 수를 기록하는 방식으로 해결했습니다.

---

코드

#include <bits/stdc++.h>
using namespace std;

int N, M;
int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

vector<vector<int>> inp_map;
vector<vector<int>> visited;

void BFS(int y, int x) {
    visited[y][x] = 1;
    queue<pair<int,int>> q;
    q.push(make_pair(y, x));

    while (!q.empty()) {
        int cy = q.front().first;
        int cx = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int ny = cy + dy[i];
            int nx = cx + dx[i];

            if (0 <= ny && ny < N && 0 <= nx && nx < M) {
                if (visited[ny][nx] == 0 && inp_map[ny][nx] == 1) {
                    visited[ny][nx] = visited[cy][cx] + 1;
                    q.push(make_pair(ny, nx));
                }
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        inp_map.push_back(vector<int>());
        visited.push_back(vector<int>());
        string tmp;
        cin >> tmp;

        for (int j = 0; j < M; j++) {
            inp_map[i].push_back(tmp[j] - '0');
            visited[i].push_back(0);
        }
    }

    BFS(0, 0);

    cout << visited[N - 1][M - 1] << "\n";
    return 0;
}

---

풀이 흐름

1. N, M을 입력받는다.
2. 문자열 형태로 주어지는 미로를 한 줄씩 입력받아 inp_map에 저장한다.
3. visited 배열은 처음에는 모두 0으로 초기화한다.
4. 시작점 (0, 0)에서 BFS를 시작한다.
5. 현재 칸에서 상하좌우 네 방향을 확인한다.
6. 범위 안에 있고, 아직 방문하지 않았으며, 이동 가능한 칸(1)이면 방문 처리한다.
7. 방문할 때 visited[현재 칸] + 1을 저장해서 거리 정보를 누적한다.
8. BFS가 끝난 뒤 visited[N-1][M-1]를 출력한다.

---

구현 포인트

1. 최소 경로 문제이므로 BFS 사용

이 문제는 각 이동의 비용이 모두 같기 때문에,

시작점에서 가까운 칸부터 차례대로 탐색하는 BFS가 잘 맞습니다.

즉, 먼저 도착하는 경로가 곧 최소 이동 횟수가 되므로

최소 칸 수를 구하는 데 BFS를 사용할 수 있습니다.

---

2. visited 배열에 방문 여부와 거리 정보를 함께 저장

보통 visited는 단순히 방문 여부만 저장하기도 하지만,

이 문제에서는 방문 여부와 함께 시작점으로부터 몇 칸째인지도 같이 저장했습니다.

visited[ny][nx] = visited[cy][cx] + 1;

이렇게 하면 별도의 거리 배열을 만들지 않아도

도착점까지의 최소 칸 수를 바로 구할 수 있습니다.

시작점은 1부터 시작하도록 했기 때문에,

마지막에 출력되는 값에는 시작 위치도 포함됩니다.

---

3. 네 방향 탐색

상하좌우 이동은 dy, dx 배열을 이용해 처리했습니다.

int dy[4] = {-1, 0, 1, 0};
int dx[4] = {0, 1, 0, -1};

이 방식은 BFS나 DFS에서 자주 사용하는 방식이라 같이 익혀두면 편합니다.

---

4. 입력이 붙어서 들어오기 때문에 문자열로 받기

미로 입력은 101111처럼 숫자가 붙어서 들어옵니다.

그래서 한 줄을 문자열로 입력받고, 각 문자를 숫자로 바꾸는 방식으로 처리했습니다.

string tmp;
cin >> tmp;

for (int j = 0; j < M; j++) {
    inp_map[i].push_back(tmp[j] - '0');
}

tmp[j] - '0'을 하면 문자 '1', '0'을 정수 1, 0으로 바꿀 수 있습니다.

---