백준 2206번 [벽 부수고 이동하기](C++) -yes6686- 티스토리

백준 문제 풀이: 2206 [벽 부수고 이동하기]

---

문제 링크: https://www.acmicpc.net/problem/2206

문제 설명:

n×m 크기의 행렬에서 (1,1)에서 (n,m)으로 이동하는 최단 경로를 찾는 문제입니다. 이동 중 벽(1)을 최대 한 번 부술 수 있으며, 벽이 없는 칸은 0으로 표시됩니다. 최단 경로의 길이를 출력하고, 이동이 불가능하면 -1을 출력합니다.

입력:

• 첫째 줄에 행렬의 크기 n, m이 주어집니다. (1 ≤ n, m ≤ 1,000)
• 둘째 줄부터 n개의 줄에 0과 1로 이루어진 행렬이 주어집니다.

출력:

• 최단 경로의 길이를 출력합니다. 이동이 불가능하면 -1을 출력합니다.

---

문제 해결 코드

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

int n, m;
int grid[1001][1001]; // 입력 행렬
int dist[1001][1001][2]; // 거리 배열 (벽을 부순 상태와 부수지 않은 상태를 구분)
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

// BFS로 최단 거리 계산
int bfs() {
    queue<tuple<int, int, int>> q; // (x, y, 벽 부순 여부)
    q.push({1, 1, 0});
    dist[1][1][0] = 1;

    while (!q.empty()) {
        auto [x, y, broken] = q.front();
        q.pop();

        if (x == n && y == m) {
            return dist[x][y][broken]; // 도착 지점에 도달한 경우 거리 반환
        }

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

            // 범위를 벗어나면 무시
            if (nx <= 0 || ny <= 0 || nx > n || ny > m) continue;

            // 벽이 아닌 경우
            if (grid[nx][ny] == 0 && dist[nx][ny][broken] == 0) {
                dist[nx][ny][broken] = dist[x][y][broken] + 1;
                q.push({nx, ny, broken});
            }

            // 벽이고 아직 벽을 부순 적이 없는 경우
            if (grid[nx][ny] == 1 && broken == 0 && dist[nx][ny][1] == 0) {
                dist[nx][ny][1] = dist[x][y][broken] + 1;
                q.push({nx, ny, 1});
            }
        }
    }

    return -1; // 도달할 수 없는 경우
}

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

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string row;
        cin >> row;
        for (int j = 1; j <= m; j++) {
            grid[i][j] = row[j - 1] - '0';
        }
    }

    cout << bfs() << '\n';
    return 0;
}

예제

입력:
6 4
0100
1110
1000
0000
0111
0000

출력:
15

입력:
4 4
0111
1111
1110
0000

출력:
-1

---

코드 설명

• BFS: 최단 거리를 탐색하며 벽을 부수지 않은 상태와 부순 상태를 구분해 각각의 거리를 관리합니다.
• 거리 배열: dist[x][y][broken]은 (x, y)에 도달했을 때의 최단 거리를 저장하며, broken은 벽을 부순 여부를 나타냅니다.
• 벽 처리: 벽을 만나면 broken == 0 상태에서만 벽을 부수고 이동할 수 있습니다.

시간 복잡도

• BFS의 시간 복잡도는 O(n × m)입니다. 입력 크기가 최대 1,000 × 1,000이므로 효율적으로 작동합니다.

---

결과

코드는 입력된 행렬에서 벽을 최대 한 번 부수며 이동할 수 있는 최단 경로를 정확히 계산합니다. BFS를 활용한 효율적인 접근 방식으로 문제를 해결합니다.

다른 테스트 사례나 개선 사항이 있다면 댓글로 공유 부탁드립니다!