📖 백준 2206번 : https://www.acmicpc.net/problem/2206
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 2 초 | 192 MB |
문제
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.
만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.
한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.
맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.
입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
출력
첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.
풀이
시간 초과를 신경쓰지 않고 생각했을 때는, 백트래킹을 활용해서 최단 경로를 구할 수 있다고 생각하고 접근했다. 하지만 1000x1000영역에서 4방향으로 이동할 수 있는 조건을 만족하면서 백트래킹을 사용하는 것은 기하급수적으로 늘어나는 경우의 수 때문에 시간 제한을 지킬 수 없었다.
가중치가 없는 그래프에서 최단경로를 탐색하는 문제이기 때문에 bfs를 사용하는 풀이로 다시 접근했다. 단순하게 bfs를 시도하면 모든 벽에 대해서 분기를 나눠서 탐색해야 때문에, 최악의 경우 nm개의 벽이 존재할 수 있으므로 O(nm*nm) 즉, O((nm)^2)만큼의 시간이 걸린다. 따라서 벽의 개수만큼 그래프 탐색을 반복하는 것이 아니라, 한번의 탐색에서 벽을 부쉈는지 부수지 않았는지 판별하며 탐색을 해야한다.
visited배열을 3차원배열로 만들어 벽을 부수고 탐색하는 경우와 벽을 부수지 않고 탐색하는 경우를 나눠서 생각했다. queue에는 x, y 좌표 뿐만아니라 depth와 is_broken변수로 현재 거리와 벽을 부쉈는지 여부를 파악하게 했다. 총 4가지 케이스를 나눠서 bfs를 적용하면 된다.
- 다음 탐색이 0이고 벽을 부수지 않은 경우
- 다음 탐색이 0이고 벽을 부순 경우
- 다음 탐색이 1이고 벽을 부수지 않은 경우
- 다음 탐색이 1이고 벽을 부순 경우
1번의 경우는 평범하게 bfs를 적용하는 경우이다.
2번은 is_broken값이 true이면서 다음 탐색이 0이다. 따라서 visited배열에서 벽을 부순 경우의 방문을 체크하게 한다.
3번은 is_broken값이 false이면서 다음 탐색이 1이다. 이 때는 is_broken을 true로 갱신하고 벽으로의 탐색을 진행한다.
4번은 이미 벽을 한번 부쉈는데 또 벽을 마주친 경우이므로 탐색하지 않는다.
총 4가지 케이스를 잘 구현해서 bfs 탐색을 진행하고 (n,m)에 도달했을 경우의 depth를 출력하면 끝이다. bfs이므로 가장 먼저 도착한 경우가 가장 depth가 작을 것이므로 탐색을 더 진행하지 않고 멈춘다.
여담으로 이 문제의 입력은 공백없이 주어지는 숫자의 나열이므로 string으로 한번에 받아서 하나씩 배열에 저장해주거나, scanf("%1d", 배열)을 통해서 하나씩 값을 받거나 하면 된다. 빠르게 풀기 위해서 ios::sync_with_stdio(false); <- 구문을 사용하는 경우에는 scanf()사용에 주의해야한다.
코드를 짤 때 c, c++의 입출력 혼용은 가능하지만, 해당 코드를 쓰면 c와 c++의 표준 stream의 동기화가 끊기기 때문에 vs에서 컴파일 했을 때는 문제가 없어 보이지만 백준 채점 프로그램 상에서는 문제가 생긴다. (출처 : https://www.acmicpc.net/board/view/104818)
모든 반례가 맞음에도 계속 틀려서 고역이었는데 이 게시글을 보고 겨우 틀린 이유를 찾았다... 이런 감사한 글들 덕분에 문제 해결에 큰 도움을 얻는다. 백준 문제에서 질문 게시판 탭이 있는데, 막힐 때마다 게시판 덕분에 반례 테스트케이스들도 많이 얻어가고 간과할 수 있는 부분들도 깨닫게 해준다. 다들 질문 게시판을 애용하면 공부에 더 도움이 될 것 같다!
코드
#include <iostream>
#include <queue>
using namespace std;
class c{
public:
c(int x, int y, int depth, bool broken) {
this->x = x;
this->y = y;
this->depth = depth;
this->is_broken = broken;
}
int x;
int y;
int depth;
bool is_broken;
};
int space[1000][1000];
bool visited[1000][1000][2];// 벽을 안부수고 이동한 경우, 부수고 이동한 경우 구분
int n, m;
int ans = -1;
void bfs() {
//상 하 좌 우
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
queue<c> q;//x,y,depth, is_broken
q.push(c(0, 0, 1, false));
visited[0][0][0] = true;
while (!q.empty()) {
c now = q.front();
q.pop();
if (now.y == n - 1 && now.x == m - 1) {// 도착시 종료
ans = now.depth;
return;
}
for (int i = 0; i < 4; i++) {
int y = now.y + dy[i];
int x = now.x + dx[i];
int next_depth = now.depth + 1;
if (x >= 0 && y >= 0 && x < m && y < n) {//범위안에 존재할 경우
if (!space[y][x] && !visited[y][x][0] && !now.is_broken) {
//다음이 0이고 벽을 부순 적이 없을 때
visited[y][x][0] = true;
q.push(c(x, y, next_depth, false));
}
else if (!space[y][x] && !visited[y][x][1] && now.is_broken) {
//다음이 0이고 벽을 부순 적이 있을 때
visited[y][x][1] = true;
q.push(c(x, y, next_depth, true));
}
else if (space[y][x] && !visited[y][x][0] && !now.is_broken) {
//다음이 1이고 벽을 부순 적이 없을 때
visited[y][x][0] = true;
q.push(c(x, y, next_depth, true));
}
}
}
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf_s("%1d", &space[i][j]);// 백준에 제출할 때는 scanf_s가 아니라 scanf로 작성해야한다.
}
}
bfs();
cout << ans;
return 0;
}