[알고리즘] 백준 2206번: 벽 부수고 이동하기 (C++), 새로운 유형 BFS + Greedy

https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

처음엔 BFS를 돌려서 큐에다가 현재의 위치와 벽을 부술 수 있는지에 대한 힘의 여부를 담았다.

그리고, 한번 방문했다면 방문할 수 없게끔 했다. (무한 루프 방지)

 

[처음 코드]

#include <iostream>
#include <queue>
#include <utility>
#include <memory.h>
using namespace std;

int n, m;
int map[1001][1001] = { 0, };
int temp[1001][1001] = { 0, };
bool visited[1001][1001] = { 0, };

typedef struct {
	int y, x;
} Direction;

Direction dir[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

void bfs(int row, int col) {
	queue<pair<pair<int, int>, bool>> q;
	q.push(make_pair(make_pair(row, col), 1));
	visited[row][col] = 1;
	temp[row][col] = 1;
	while (!q.empty()) {
		int y = q.front().first.first;
		int x = q.front().first.second;
		int pow = q.front().second;

		q.pop();
		for (int i = 0; i < 4; i++) {
			int dy = y + dir[i].y;
			int dx = x + dir[i].x;
			if (dy >= 1 && dy <= n && dx >= 1 && dx <= m) {
				if (!visited[dy][dx]) {
					if (map[dy][dx] == 1 && pow == 1) {
						visited[dy][dx] = 1;
						q.push(make_pair(make_pair(dy, dx), 0));
						temp[dy][dx] = temp[y][x] + 1;
					}
					else if (map[dy][dx] == 0) {
						visited[dy][dx] = 1;
						q.push(make_pair(make_pair(dy, dx), pow));
						temp[dy][dx] = temp[y][x] + 1;
					}
				}
			}
		}
	}
}

int main() {
	cin >> n >> m;
	memset(temp, -1, sizeof(temp));
	for (int i = 1; i <= n; i++) {
		string value;
		cin >> value;
		for (int j = 1; j <= m; j++) {
			map[i][j] = value[j - 1] - '0';
		}
	}

	bfs(1, 1);
	cout << temp[n][m];
	return 0;
}

하지만, 이럴 경우 반례가 발생한다.

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100
[answer]
29
[output]
-1

다음 오류가 발생하는 이유는 아래 그림과 같다.

이유는 방문을 체크하기 때문에 발생한다.

(1, 1)에서 시작하면 오른쪽에 벽을 부숴서 (1, 3)으로 갈 수 있다. 그럼 이미 방문이 되어있는 상태다.

>> (빨간색 화살표)

하지만, 내가 생각하는 최적의 경로는 저 때 벽을 부수지 않고, 6행의 벽을 부숴서 넘어가는 것이다.

>> (초록색 화살표)

[반례 모음집]

(https://www.acmicpc.net/board/view/66299)

 

>> 그렇다고 해서 방문을 체크할 수 없다면 무한 루프를 발생시키는데 어떻게 해야 할까?

---

솔루션

여러 솔루션을 참고하다가 다음 결론이 내려졌다.

>> 벽을 부수고, 도달한 좌표에 벽을 안 부수고, 도달한 방법이 있다면 후자를 택하면 되겠다.

>> 그래야 위의 반례 같은 사례를 처리할 수 있을 거라는 생각이 들었다.

 

즉, 어떤 좌표값이 있으면 그 좌표값에 도달하는 방법은 2가지다.

벽을 한 번 부수고 왔는가 or 벽을 안 부수고 왔는가

 

그래서 visited로 방문 체크를 할 겸 경로 값도 담고, 힘을 쓰고 왔는지 안 쓰고 왔는지에 대한 여부도 따질 생각이다.

[visited의 역할]

• 방문 체크
• 경로 값 담기
• 힘 사용 여부 체크

그래서 3차원 배열로 이번 문제를 solve 한다.

어떠한 좌표값에 힘을 아직 안 썼다면 visited[좌표][좌표][0]에다가 값을 넣을 것이고,

힘을 썼다면 visited[좌표][좌표][1]에다가 값을 넣을 것이다.

 

세 가지 변수를 다루기 때문에 구조체 변수를 선언했다.

typedef struct {
	int y, x;
	int power; // 힘을 썼는가 안 썼는가
} Move;

그리고, BFS에서는 (n, m)에 도달하면 경로 값을 리턴하는 방식으로 코드를 작성했다.

BFS가 끝나면 -1 리턴 >> 도달하지 못했다는 거니까

 

[AC 코드]

#include <iostream>
#include <queue>
#include <utility>
#include <memory.h>
using namespace std;

int n, m;
int map[1001][1001] = { 0, };
int visited[1001][1001][2];

typedef struct {
	int y, x;
} Direction;

Direction dir[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };

typedef struct {
	int y, x;
	int power; // 힘을 썼는가 안 썼는가
} Move;

int bfs(int row, int col) {
	queue<Move> q;
	q.push({row, col, 0});
	visited[row][col][0] = 1;
	while (!q.empty()) {
		Move now = q.front();

		q.pop();

		if (now.y == n && now.x == m) {
			return visited[now.y][now.x][now.power];
		}
		for (int i = 0; i < 4; i++) {
			Move next;
			next.y = now.y + dir[i].y;
			next.x = now.x + dir[i].x;
			next.power = now.power;
			if (next.y >= 1 && next.y <= n && next.x >= 1 && next.x <= m) {
				if (!visited[next.y][next.x][next.power]) {
					if (map[next.y][next.x] == 0) {
						visited[next.y][next.x][next.power] = visited[now.y][now.x][now.power] + 1;
						q.push(next);
					}
					if (map[next.y][next.x] == 1 && next.power == 0) {
						next.power = 1; // 힘을 썼다.
						visited[next.y][next.x][next.power] = visited[now.y][now.x][now.power] + 1;
						q.push(next);
					}
				}
			}
		}
	}

	return -1;
}

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

	cout << bfs(1, 1);

	return 0;
}

---

느낀 점

이번 문제는 BFS의 새로운 유형이었다.

기존에는 방문 체크, 좌표값을 챙겼다면 이번에는 힘을 사용했는지 안 사용했는지 또한 따져야 했다.

그래서 어떻게 보면 visited 2차원 배열을 2개 선언하여 하나는 힘을 안 쓴 것과 힘을 쓴 것으로 나누어서 BFS를 돌려도 되겠다 생각이 들었다.

꽤 어려운 문제였다.

무조건 업 솔빙 해야 한다.

 

https://www.acmicpc.net/board/view/27386

글 읽기 - ★☆★☆★ [필독] 벽 부수고 이동하기 FAQ ★☆★☆★

솔루션을 구글링 하면서 좋은 글을 발견했다. 어떠한 코드에 대해 더 논리적으로 심층적인 분석을 해둔 글이다.