백준 2206번: 벽 부수고 이동하기 - BFS 최단 거리 문제 정리

백준 2206번: 벽 부수고 이동하기 - BFS 최단 거리 문제 정리

🔹 문제 개요

백준 2206번 "벽 부수고 이동하기" 문제는 최단 경로 탐색 문제로, 주어진 N x M 크기의 맵에서 (1,1) → (N,M)으로 이동하는 최단 거리를 구하는 문제입니다. 단, 이동 중 한 개의 벽을 부술 수 있는 기회가 제공됩니다.

🔹 해결 방법

• BFS (너비 우선 탐색) 알고리즘을 사용하여 최단 거리를 탐색합니다.
• 각 위치에서 벽을 부순 경우와 부수지 않은 경우를 따로 관리하여 탐색해야 합니다.
• visited[x][y][wall] 배열을 사용하여 방문 여부를 체크합니다.
  • wall == 0: 벽을 부수지 않은 상태
  • wall == 1: 벽을 한 번 부순 상태

---

🔹 C++ 코드 구현

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

#define MAX 1000

int n, m;
int dx[4] = { 0, 0, 1, -1 };  // 이동 방향 (상하좌우)
int dy[4] = { 1, -1, 0, 0 };

int bfs(vector<string>& v1) {
    queue<pair<pair<int, int>, pair<int, int>>> q;
    vector<vector<vector<bool>>> visited(n, vector<vector<bool>>(m, vector<bool>(2, false)));

    q.push({ {0, 0}, {0, 1} }); // {{x, y}, {벽 부숨 여부, 거리}}
    visited[0][0][0] = true;

    while (!q.empty()) {
        int x = q.front().first.first;
        int y = q.front().first.second;
        int wall = q.front().second.first;
        int dist = q.front().second.second;
        q.pop();

        // 도착 지점 도달 시 최단 거리 반환
        if (x == n - 1 && y == m - 1) {
            return dist;
        }

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

            // 범위 내에서만 이동 가능
            if (nx >= 0 && nx < n && ny >= 0 && ny < m) {
                // 벽이 없는 경우
                if (v1[nx][ny] == '0' && !visited[nx][ny][wall]) {
                    visited[nx][ny][wall] = true;
                    q.push({ {nx, ny}, {wall, dist + 1} });
                }
                // 벽이 있는 경우 (벽을 한 번도 부수지 않았다면 부수고 이동)
                else if (v1[nx][ny] == '1' && wall == 0 && !visited[nx][ny][1]) {
                    visited[nx][ny][1] = true;
                    q.push({ {nx, ny}, {1, dist + 1} });
                }
            }
        }
    }

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

int main() {
    cin >> n >> m;
    vector<string> v1(n);

    for (int i = 0; i < n; i++) {
        cin >> v1[i];
    }

    cout << bfs(v1) << endl;

    return 0;
}

---

🔹 코드 설명

1. 입력 받기: N x M 크기의 맵을 입력받습니다.
2. BFS 탐색을 위한 큐 생성:
   • (x, y, 벽 부숨 여부, 현재 거리) 형식으로 탐색
   • visited[x][y][0] → 벽을 부수지 않고 방문한 경우
   • visited[x][y][1] → 벽을 부수고 방문한 경우
3. BFS 탐색 진행:
   • 벽이 없는 경우: 그대로 이동
   • 벽이 있는 경우: 벽을 부술 기회가 있으면 한 번 부수고 이동
4. 최단 거리 도달 시 반환
   • (N-1, M-1) 위치에 도착하면 최단 거리 출력
   • 도착할 수 없으면 -1 반환

---

🔹 시간 복잡도 분석

• BFS는 O(NM)의 시간 복잡도를 가집니다.
• visited 배열을 사용하여 중복 탐색을 방지하여 최적화된 탐색을 수행합니다.

---

🔹 예제 테스트

입력 예시

6 4
0100
1110
1000
0000
0111
0000

출력 예시

15

---

🔹 핵심 요약

✅ BFS를 사용하여 최단 경로를 탐색 ✅ 벽을 부수고 이동할 수 있는 경우를 따로 관리 ✅ visited[x][y][wall] 배열을 활용하여 상태 구분 ✅ 도착 가능하면 최단 거리, 불가능하면 -1 반환

---

이 코드로 백준 2206번: 벽 부수고 이동하기 문제를 효과적으로 해결할 수 있습니다! 🚀