[백준/C++] 2206번: 벽 부수고 이동하기

문제

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

---

문제 요약

N × M 행렬로 표현되는 맵에서 0은 이동할 수 있는 곳을, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다.

 

(1, 1)에서 (N, M)으로 최단 경로로 이동하려 할 때, 벽을 1개 부술 수 있다.

 

한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

---

코드

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <tuple>

using namespace std;

int n, m;
int board[1010][1010];
bool visited[1010][1010][2];

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

// x, y, dist, wall
queue<tuple<int, int, int, int>> q;

int bfs() {

    // 초기 값 큐에 삽입
    q.push({ 0, 0, 1, 0 });
    visited[0][0][0] = true;

    while (!q.empty()) {
        // 큐에서 경우의수 한 가지 뽑기
        int x, y, dist, wall;
        tie(x, y, dist, wall) = q.front();
        q.pop();

        // 도착지에 도달한 경우
        if (x == n - 1 && y == m - 1) {
            return dist;
        }

        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            // 경계를 벗어난 경우
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;

            // 벽을 만나면 벽을 부술 수 있는지 확인
            if (board[nx][ny] == 1 && wall == 0 && !visited[nx][ny][1]) {
                visited[nx][ny][1] = true;
                q.push({ nx, ny, dist + 1, 1 });
            }
            // 벽이 아닌 경우
            else if (board[nx][ny] == 0 && !visited[nx][ny][wall]) {
                visited[nx][ny][wall] = true;
                q.push({ nx, ny, dist + 1, wall });
            }
        }
    }
    return -1; // 도착지에 도달할 수 없는 경우
}

int main() {
    cin >> n >> m;

    // 입력
    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        for (int j = 0; j < m; j++) {
            board[i][j] = str[j] - '0';
        }
    }

    cout << bfs() << "\n";

    return 0;
}

---

코드 설명

(1, 1)부터 (N, M)까지 BFS로 최단 거리를 탐색한다.

 

이때, 벽을 1번 부술 수 있으므로,이를 체크하기 위한 변수 wall과 해당 좌표에서 벽을 부순 적이 있는지를 체크하기 위한 배열 visited를 이용한다.

 

이동할 좌표를 탐색하는 조건은 다음과 같다.

 

1. 행렬의 범위를 벗어날 경우는 제외한다.

 

2. 현재 좌표가 벽이면, 부순 적이 없고, 부술 수 있는지 확인한다.

 

3. 현재 좌표가 벽이 아니면, 방문한 적이 없는지 확인한다.

 

---

고찰

DFS는 보통 모든 경로를 탐색하는 데 사용된다.

+ 가능하지만, 시간 복잡도가 높아질 수 있다.

 

최단 경로를 탐색하는 문제에서는 BFS가 일반적으로 사용된다는 점을 잊지 말자.