백준 2206 - 벽 부수고 이동하기
문제 요약
N×M 맵에서 (0,0) → (N-1,M-1)까지 이동할 때, 벽을 최대 1번 부수고 이동할 수 있다.
최단 경로의 길이를 구하고, 불가능하면 -1을 출력한다.
첫 번째 아이디어 — 모든 벽마다 BFS?
처음엔 벽마다 하나씩 부수고 BFS를 돌리는 방법을 생각할 수 있다.
- 벽의 수: 최대 O(N×M)
- BFS 한 번: O(N×M)
- 전체: O(N²M²) → N, M = 1000이면 10¹² → 완전히 시간 초과
다른 접근이 필요하다.
핵심 아이디어 — 3차원 visited
BFS를 한 번만 돌리되, "벽을 뚫었는지 여부"를 상태에 포함시킨다.
struct Point {
int x, y;
bool broken; // 지금까지 오는 경로에서 벽을 뚫은 적 있는가
};
이렇게 하면 같은 칸이라도 두 가지 상태가 존재한다.
(x, y, broken=false): 벽을 아직 안 뚫고 이 칸에 도착(x, y, broken=true): 벽을 이미 뚫고 이 칸에 도착
따라서 visited 배열은 3차원이어야 한다.
bool visited[N][M][2];
// visited[x][y][0] = 벽 안 뚫고 (x,y)에 온 적 있음
// visited[x][y][1] = 벽 뚫고 (x,y)에 온 적 있음
만약 2차원 배열만 쓴다면?
010
000
위 맵에서 (0,2)에 도달하는 두 경로:
(0,0)→(1,0)→(1,1)→(1,2)→(0,2): 벽 안 뚫음(0,0)→(0,1) 벽 뚫기→(0,2): 벽 뚫음
2차원 배열이면 이 둘을 구분하지 못해서 경로 하나가 무시된다.
Layer로 시각화하기
3차원을 억지로 상상하는 것보다, 평행한 2개의 2D 맵으로 생각하면 훨씬 쉽다.
┌─────────────────────┐
│ Layer 0 │ ← 벽을 아직 안 뚫은 상태로 이동하는 맵
│ (벽 못 뚫음) │
└─────────────────────┘
│
│ 벽을 만나면 (1회 한정)
▼
┌─────────────────────┐
│ Layer 1 │ ← 벽을 이미 뚫은 상태로 이동하는 맵
│ (벽 뚫은 이후) │
└─────────────────────┘
- Layer 0에서 빈 칸 이동 → Layer 0에서 계속
- Layer 0에서 벽을 만남 → Layer 1로 점프 (여러 곳에서 발생 가능)
- Layer 1에서 빈 칸 이동 → Layer 1에서 계속
- Layer 1에서 벽을 만남 → 이미 뚫었으니 스킵
최종 답은 두 레이어 중 (N-1, M-1)에 도달한 거리.
둘 다 도달했다면 min을 취한다.
최종 코드
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct Point {
int x;
int y;
bool broken;
};
int main() {
int N, M; cin >> N >> M;
vector<vector<int>> arr(N, vector<int>(M));
bool visited[1000][1000][2] = {};
int distance[1000][1000][2] = {};
for(int i = 0; i < N; i++) {
string s; cin >> s;
for(int j = 0; j < s.size(); j++) arr[i][j] = s[j] - '0';
}
queue<Point> q;
q.push({0, 0, false});
visited[0][0][0] = true;
distance[0][0][0] = 1;
while(!q.empty()) {
auto [x, y, broken] = q.front(); q.pop();
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
for(int i = 0; i < 4; i++) {
int nx = x + dx[i]; int ny = y + dy[i];
if(0 <= nx && nx < N && ny >= 0 && ny < M) {
if(arr[nx][ny] == 1) {
// 벽인 경우: 아직 안 뚫었을 때만 뚫기 가능
if(!broken) {
if(visited[nx][ny][1] == false) {
visited[nx][ny][1] = true;
distance[nx][ny][1] = distance[x][y][0] + 1;
q.push({nx, ny, true});
}
}
} else {
// 빈 칸: 현재 broken 상태 그대로 이동
if(!broken) {
if(visited[nx][ny][0] == false) {
visited[nx][ny][0] = true;
distance[nx][ny][0] = distance[x][y][0] + 1;
q.push({nx, ny, broken});
}
} else {
if(visited[nx][ny][1] == false) {
visited[nx][ny][1] = true;
distance[nx][ny][1] = distance[x][y][1] + 1;
q.push({nx, ny, broken});
}
}
}
}
}
}
if(visited[N-1][M-1][0] == true) {
if(visited[N-1][M-1][1] == true) cout << min(distance[N-1][M-1][0], distance[N-1][M-1][1]);
else cout << distance[N-1][M-1][0];
} else if(visited[N-1][M-1][1] == true) {
cout << distance[N-1][M-1][1];
} else {
cout << -1;
}
return 0;
}
구현 포인트
벽 뚫는 순간 distance 참조 주의
벽을 뚫는 순간 broken이 0→1로 전환된다.
이전 거리는 반드시 distance[x][y][0]에서 가져와야 한다.
distance[nx][ny][1] = distance[x][y][0] + 1; // [0]에서 가져옴!
distance[x][y][1]로 쓰면 아직 기록되지 않은 값(0)을 참조하게 된다.
시작점 distance 초기화
distance[0][0][0] = 1;
(0,0)을 1로 잡고 시작해야 이동할 때마다 +1로 자연스럽게 누적된다.
0으로 시작하면 마지막에 +1 보정이 필요해서 코드가 지저분해진다.
개선 포인트
1. visited 배열 없애기
distance == 0을 미방문 체크로 활용하면 배열 하나를 줄일 수 있다.
시작점을 distance[0][0][0] = 1로 잡았기 때문에, 0이면 아직 방문 안 한 것이 보장된다.
// before: visited 체크 후 marking, 따로 distance 업데이트
if(visited[nx][ny][broken] == false) {
visited[nx][ny][broken] = true;
distance[nx][ny][broken] = distance[x][y][broken] + 1;
q.push({nx, ny, broken});
}
// after: distance 하나로 통합
if(distance[nx][ny][broken] == 0) {
distance[nx][ny][broken] = distance[x][y][broken] + 1;
q.push({nx, ny, broken});
}
2. 도착 즉시 return
BFS는 레이어 순으로 탐색하므로 처음 도착한 순간이 최단거리다.
현재 코드는 큐가 빌 때까지 탐색을 계속하지만, 도착 즉시 반환하면 불필요한 탐색을 줄인다.
auto [x, y, broken] = q.front(); q.pop();
if(x == N-1 && y == M-1) return distance[x][y][broken];
3. 입출력 최적화
ios::sync_with_stdio(false);
cin.tie(nullptr);
C++ 입출력과 C 입출력의 동기화를 끊어 속도를 높인다.
위 개선들을 합쳐서 실제 채점 시간이 약 50ms 단축됐다.
시간복잡도
- 상태 수: N × M × 2
- 각 상태를 한 번씩만 방문
- O(N × M)