https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로
www.acmicpc.net
엄청 어려운 문제는 아니지만 뭔가 한 번 더 생각해 볼만한 내용이 있는 문제였기에 정리해보려고 한다.
이 문제는 그래프 탐색 문제에서 조건이 하나 더 주어진다. 경로를 탐색하는 중에 벽을 한번 넘어갈 수 있다는 것이다. 따라서 요지는 경로를 탐색하는 중에 어떤 식으로 벽을 뚫었는 지를 저장할 지가 관건이다.
처음에는 BFS로는 풀 수 없는 문제라고 판단했다. 그 이유는 두 가지.
1. 벽을 부쉈는지 부수지 않은 경로인지 저장하기 어려움
2. DFS를 이용하면 재귀를 이용하여 쉽게 확인이 가능함
위의 두가지 이유 때문에 DFS로 풀이를 시도하였다.
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>
#include <stack>
using namespace std;
// bfs로 불가능한 이유 -> 벽을 부쉈는지 부수지 않은 경로인지 확인하기 어려움
// dfs를 이용 -> 만약 도착하지 못했는데 막힌경우 인접한 벽을 하나 부순다 -> 그러고도 도착하지 못하면 원래위치 복귀
// 벽을 부순 횟수를 기록하는 방법... 두가지 경우가 존재, 1. 벽을 부수고 벽을 부순 이후 지점으로 복귀하는 경우 2. 벽을 부수고 벽을 부수기 이전 지점으로 복귀하는 경우, 구분이 안됨 --> 매개 변수!
struct Pos {
int X;
int Y;
};
int frontX[4]{ 1, -1, 0, 0 };
int frontY[4]{ 0, 0, 1, -1 };
int N, M;
vector<vector<char>> map(1001, vector<char>(1001, '0'));
vector<vector<int>> discovered(1001, vector<int>(1001, 0));
int minValue = INT_MAX;
void input() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> map[i][j];
}
}
}
void dfs(Pos curPos, bool isCrashed) {
if (curPos.X == M - 1 && curPos.Y == N - 1) { // 도착
minValue = min(minValue, discovered[curPos.Y][curPos.X]);
return;
}
for (int i = 0; i < 4; i++) {
Pos nextPos{ curPos.X + frontX[i], curPos.Y + frontY[i] };
// 맵 안에 있는지
if (nextPos.X < M && nextPos.Y < N && nextPos.X >= 0 && nextPos.Y >= 0) {
// 갈 수 있는 지점인지 or 벽을 부술 기회가 있는 지
if (map[nextPos.Y][nextPos.X] == '0') {
// 이미 발견한 지점인지
if (discovered[nextPos.Y][nextPos.X] == 0) {
// 방문
discovered[nextPos.Y][nextPos.X] = discovered[curPos.Y][curPos.X] + 1;
dfs(nextPos, isCrashed);
discovered[nextPos.Y][nextPos.X] = 0;
}
}
else if(map[nextPos.Y][nextPos.X] == '1') {
if (isCrashed == false) { // 한번 부순다
// 이미 발견한 지점인지
if (discovered[nextPos.Y][nextPos.X] == 0) {
// 방문
discovered[nextPos.Y][nextPos.X] = discovered[curPos.Y][curPos.X] + 1;
dfs(nextPos, true);
discovered[nextPos.Y][nextPos.X] = 0;
}
}
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
input();
discovered[0][0] = 1;
dfs(Pos{ 0, 0 }, false);
if (minValue == INT_MAX) {
cout << -1 << endl;
}
else {
cout << minValue << endl;
}
}
DFS를 이용해서 풀었지만 이 코드는 시간초과가 나온다. 애초에 DFS는 넉넉한 시간을 염두하고 사용이 가능하나 이 문제느 아니였던 것. 결국 정답 코드를 좀 참고했는데, 대부분 BFS로 푼것을 확인할 수 있었다. 그래서 이후에 BFS로 문제를 다시 접근하였다.
#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>
#include <stack>
using namespace std;
// 벽(1)에 대해 한번까지 큐에 추가하고 그 다음에 벽을 만나는 경우는 그만
struct Pos {
int X;
int Y;
int isCrashed = 0;
};
int frontX[4]{ 1, -1, 0, 0 };
int frontY[4]{ 0, 0, 1, -1 };
int N, M;
int ans;
char map[1001][1001];
int discovered[1001][1001][2];
queue<Pos> bfsQueue;
void input() {
cin >> N >> M;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
cin >> map[i][j];
}
}
}
int bfs() {
discovered[0][0][0] = 1;
bfsQueue.push(Pos{ 0, 0, 0 });
while (bfsQueue.empty() == false) {
Pos curPos = bfsQueue.front();
bfsQueue.pop();
// 도착
if (curPos.X == M - 1 && curPos.Y == N - 1) {
return discovered[N - 1][M - 1][curPos.isCrashed];
break;
}
for (int i = 0; i < 4; i++) {
Pos nextPos{ curPos.X + frontX[i], curPos.Y + frontY[i], curPos.isCrashed };
// 맵에 있는지
if (nextPos.X < M && nextPos.Y < N && nextPos.X >= 0 && nextPos.Y >= 0) {
// 갈 수 있는지
if (map[nextPos.Y][nextPos.X] == '0' && discovered[nextPos.Y][nextPos.X][nextPos.isCrashed] == 0) {
// 발견
discovered[nextPos.Y][nextPos.X][nextPos.isCrashed] = discovered[curPos.Y][curPos.X][nextPos.isCrashed] + 1;
bfsQueue.push(Pos{ nextPos.X, nextPos.Y, curPos.isCrashed });
}
else if (map[nextPos.Y][nextPos.X] == '1' && curPos.isCrashed == 0) { // 벽을 부술 수 있을 때
// 발견
discovered[nextPos.Y][nextPos.X][1] = discovered[curPos.Y][curPos.X][0] + 1;
bfsQueue.push(Pos{ nextPos.X, nextPos.Y, 1 });
}
}
}
}
return -1;
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
input();
cout << bfs() << endl;
}
처음에 BFS로 하는것이 불가능하다고 판단했던 이유는 벽을 통과한 경로인지 아닌지 확인이 어렵다는 것이었다. 게다가 Pos 구조체에 벽을 뚫었는 지에 대한 여부를 이용하여 벽 통과 여부를 저장하였는데 18%에서 메모리 초과가 났다.
메모리 초과가 난 이유는 명확했다. 이미 방문한 지점에 대해 확인하는 코드를 넣지 않아서 bfsQueue에 계속해서 방문할 노드가 추가되었기 때문이다. 하지만 이미 방문한 지점에 대한 코드를 확인하는 코드를 넣게되면 특정한 경우에 경로를 찾을 수 없게 된다.
https://www.acmicpc.net/board/view/106323
글 읽기 - 2206번 bfs풀이 왜틀릴까요ㅜ
댓글을 작성하려면 로그인해야 합니다.
www.acmicpc.net
대표적으로 위의 예시에서 경로를 찾지 못해 -1이 출력된다. 그렇다면 방법이 무엇인가? 단순히 방문 체크를 2가지를 나눠서 하면 된다.
방문체크로 사용하는 dicovered 배열을 3차 배열로 선언하여 벽을 허물지 않은 경로와 벽을 허물고 지나가는 경로를 나눠서 기록하는 것이다.
정리하면 벽을 뚫지 않았을 때에는 0번 배열에 기록하다가 벽을 뚫은 순간부터는 1번 배열에 기록하는 방식이다. 그렇게 해도 되는 건가 싶었는데, 조금만 더 생각해보면 이게 정답이구나를 알 수 있다.
위에서 언급된 문제점은 벽을 허물고 지나가는 경로와 허물지 않고 지나가는 경로가 충돌되어서 발생하는 문제인데 아예 따로 저장을 해버리면 두 가지 경우의 경로가 서로 충돌하지 않는다. 즉, 경로를 허물지 않고 지나가는 세계와 경로를 허물고 지나가는 세계를 아예 분리하여 생각하는 것이 관건이었다고 생각한다.