백준 2206번 C++ 풀이

문제

 

시간 제한	메모리 제한	solved.ac 티어
2초	192MB	골드 3

---

풀이

 이 문제 유형은 예전부터 도전해보고 싶은 유형이었다. 단순히 그래프를 탐색하여 최단경로를 찾는 것이 아닌, 벽을 부수거나 뛰어넘는 등의 지나갈수 없는 길을 조건적으로 지나가는 문제유형은 생각해야하는 것이 정말 많기 때문이다. 사실 전에 의도치 않게 이런 류의 문제의 풀이 일부를 지인에게 스포당했다. 같이 랜덤 실버 디펜스를 하고 있었는데, 이와 비슷한 문제를 시도했다가 실패했고, 지인에게 풀이법을 듣게 되었다. 하지만 그 지인의 말로는 이 풀이를 들었다고 이런 유형의 문제를 다 풀수 있는게 아니라는 말을 듣고 일단은 알겠다고 한 기억이 있다. 스포당한지 어언 5개월 후, 다른 문제인 이 문제를 풀게 되었다. 스포를 당해서 풀이법을 작성하긴 했지만, 여전히 까다로운 문제였다.

 

 풀이법은 보통의 BFS라면 거리와 다음 위치정보를 저장하는 것이 일반적이다. 하지만 문제 유형이 유형인 만큼, 하나의 정보를 더 저장한다. 바로 벽을 부순 개수이다. 해당 문제는 벽을 1개까지 부술수 있기 때문에 벽을 부쉈는지 안부쉈는지(true/false)를 저장해도 될 것이다. 하지만 벽을 여러번 부수는 문제가 나올 수도 있기 때문에 필자는 개수로 저장하도록 하겠다.

 내가 방문하려는 곳을 방문했는지 체크하며, 벽을 부수지 않은 상태에서 벽을 만났다면 벽을 1개 부수면 될 것이고, 벽을 부순 상태에서 벽을 만났다면 방문하지 않으면 될 것이다. 여기서 한가지 문제가 생긴다. 도착지에 가기 전인 중간 지점 A를 지나고 있다고 생각해보자. A지점에 오기 전에는 벽을 부수고 오는 경로도 있고 그렇지 않은 경로가 모두 존재한다. 벽을 부수고 A지점에 오며 먼저 방문 처리를 해버렸다면, 벽을 부수지 않고 A지점에 올 수 있음에도 오지 못하는 경우가 생긴다. 이런 상황에서 도착지 주변으로 벽이 한겹씩 둘러져 있다고 해보자. 우리는 도착지까지 갈 수 있음에도 가지 못한다고 판단하는 WA가 나올수 있다. A에서 도착지까지 벽을 한개만 부수면 되는 경우에 말이다. 그렇기에 우리는 방문체크를 하는 배열을 조금 수정할 필요가 있어보인다.

 visited배열에 단순히 방문했는지 아닌지를 저장하는 것이 아닌, 해당 지점까지 벽을 몇개를 부수고 왔는지를 저장한다. 만약 방문하지 않은 상태라면 -1을 저장하면 될 것이다. 이제 다음으로 방문할 지점의 visited값이 -1이라면 그냥 방문하면 될 것이다. 하지만 visited값이 0이라면 방문할 필요가 없어질 것이다. 이미 해당 지점까지 벽을 부수지 않고 오는 경로가 존재한다는 뜻일테니 말이다. visited값이 1이라면 현재까지 오기까지 벽을 몇개를 부쉈는지에 따라 방문여부를 결정해야한다. 현재까지 벽을 부수지 않고 왔다면 방문하려는 곳에 더 효율적으로, 그러니까 벽을 더 적게 부수고 최단거리로 왔다는 뜻일테니 말이다. 만약 똑같이 벽을 부수고 왔다면 굳이 방문할 필요가 없을 것이다. 이를 일반화하면 visited값이 n이라면 현재 위치까지 오기까지 n보다 적은 벽을 부쉈다면 방문할 필요가 생기는 것이다. 하지만 n개 이상의 벽을 부수고 왔다면 굳이 방문할 필요가 없는 것이다. 이를 파악했다면 bfs에 적용하면 문제를 풀 수 있을 것이다.

코드

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<string> graph;

void input() {
	cin >> n >> m;
	graph.resize(n);
	for(auto& row : graph) cin >> row;
}

void sol() {
	queue<tuple<int,int,int,int>> q; // 거리, 다음위치 row, col, 벽부순개수
	vector<vector<int>> visited(n, vector<int>(m, -1)); // -1 : 방문안함 0 : 벽안부수고 방문 1 : 벽 부수고 방문
	int dx[4] = {1, 0, -1, 0};
	int dy[4] = {0, 1, 0, -1};
	int ans = -1;

	q.push({1, 0, 0, 0});
	visited[0][0] = 0;

	while(!q.empty()) {
		auto [cur_dist, cur_row, cur_col, break_cnt] = q.front();
		q.pop();

		if (cur_row == n - 1 && cur_col == m - 1) {
			ans = cur_dist;
			break;
		}

		for(int d = 0; d < 4; d++) {
			int nxt_row = cur_row + dy[d];
			int nxt_col = cur_col + dx[d];

			if (nxt_row < 0 || nxt_row >= n ||
				nxt_col < 0 || nxt_col >= m ||
				visited[nxt_row][nxt_col] == 0 ||
				(visited[nxt_row][nxt_col] >= 1 && visited[nxt_row][nxt_col] <= break_cnt) ||
				(break_cnt == 1 && graph[nxt_row][nxt_col] == '1')
			) continue;

			if (graph[nxt_row][nxt_col] == '0') {
				visited[nxt_row][nxt_col] = break_cnt;
				q.push({cur_dist + 1, nxt_row, nxt_col, break_cnt});
			}
			else {
				visited[nxt_row][nxt_col] = break_cnt + 1;
				q.push({cur_dist + 1, nxt_row, nxt_col, break_cnt + 1});
			}
		}
	}

	cout << ans;
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	input();
	sol();
}