백준 2206번: 벽 부수고 이동하기 (C++)

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

2206번: 벽 부수고 이동하기

 

설정은 단순하다. 0이 갈 수 있는 길이고, 1이 벽인데, 벽이 있는 곳을 딱 한 번 부시고 지나갈 수 있다.

 

이것을 구현하면 되는 것인데

 

처음에는 단순하게 구조체를 선언해서, 벽을 부실 수 있는 상태인지 관리했다.

 

즉 한 번 벽을 부수면 앞으로는 벽을 부실 수 없는 것이다.

 

이것을 구현한 결과는 아래와 같다. 이렇게 구현하지 말라고 보여주는 것이고 잘못된 코드이다

 

7 4
0000
1110
0000
0111
0000
0011
0010

 

이것이 반례가 될 수 있다.

 

#include<iostream>
#include<string>
#include<queue>
using namespace std;
int m[1002][1002], N, M, dis[1002][1002];
struct info {
	int row;
	int col;
	bool brkAbl;
};
queue<info> q;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { -1,1,0,0 };
 void bfs(pair<int, int> start) {
	q.push({start.first, start.second, true});
	dis[start.first][start.second]++;
	while (!q.empty()) {
		info cur = q.front();
		q.pop();
		cout << '\n'; cout << '\n';
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				cout << dis[i][j] << ' ';
			}
			cout << '\n';
		}
		for (int i = 0; i < 4; i++) {
			
			int nr = cur.row + dr[i];
			int nc = cur.col + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > M || dis[nr][nc] > 0) continue;
			
			//벽만났는데, 벽을 부실 수 있는 경우
			if (m[nr][nc] == 1 && cur.brkAbl) {
				//cur.brkAbl = false;
				q.push({ nr, nc, false });
				dis[nr][nc] = dis[cur.row][cur.col] + 1;
			}
			//벽이 아닌 경우 -> 현재 상태의 벽부시기 가능 여부를 같이 넘겨줌
			else if (m[nr][nc] == 0) {
				q.push({ nr, nc, cur.brkAbl });
				dis[nr][nc] = dis[cur.row][cur.col] + 1;
			}
		}
	}
}
int main(void) {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		string temp;
		cin >> temp;
		for (int j = 1; j <= M; j++) {
			m[i][j] = temp[j - 1] - '0';
		}
	}
	bfs({ 1, 1 });
	if (dis[N][M] != 0)
		cout << dis[N][M] << '\n';
	else
		cout << -1 << '\n';
	return 0;
}

 

그런데 문제가 있다. 상황이 단순하지 않은 것이, 특정 지점까지 갈 때, 벽을 부시는 것이 최단 경로가 될 수 있다.

 

이때, 특정 지점까지 벽을 부수고 최단으로 갔는데, 정작 끝까지 도달하려면 벽을 반드시 부숴야 하는 경우가 있다.

 

즉 조금 더 길게 가더라도, 마지막에 도착지까지 가려면 벽을 부수지 않아야 한다는 것이다.

 

따라서 단순히 벽을 부실 수 있는지 아닌지 여부만 관리할 게 아니라, 벽을 부수었다는 것과 방문처리(거리) 관리를 동시에 해주어야 한다는 것이다.

 

 

#include<iostream>
#include<string>
#include<queue>
using namespace std;
int m[1002][1002], N, M, dis[1002][1002][2];
struct info {
	int row;
	int col;
	int blk; //1이면 부시기 가능
};
queue<info> q;
int dr[4] = { 0,0,1,-1 };
int dc[4] = { -1,1,0,0 };
 void bfs() {
	q.push({ 1,1,1 });
	dis[1][1][1] = 1; //벽부시기 가능이니까 [1]에 넣음


	while (!q.empty()) {
		info cur = q.front();
		q.pop();
		
		if (cur.row == N && cur.col == M) {
			cout << dis[cur.row][cur.col][cur.blk] << '\n';
			return;
		}

		for (int i = 0; i < 4; i++) {
			
			int nr = cur.row + dr[i];
			int nc = cur.col + dc[i];

			if (nr < 1 || nc < 1 || nr > N || nc > M) continue;
			
			//벽 만났는데 부실 수 있는 경우
			if (m[nr][nc] == 1 && cur.blk == 1) {
				q.push({ nr, nc, 0 }); //이후로는 부실수 없음
				dis[nr][nc][0] = dis[cur.row][cur.col][1] + 1;
			}
			//벽 아닌 경우
			else if (m[nr][nc] == 0 && dis[nr][nc][cur.blk] == 0) {
				q.push({ nr, nc, cur.blk });
				dis[nr][nc][cur.blk] = dis[cur.row][cur.col][cur.blk] + 1;
			}
		}
	}
	cout << -1 << '\n';
	return;
}
int main(void) {
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		string temp;
		cin >> temp;
		for (int j = 1; j <= M; j++) {
			m[i][j] = temp[j - 1] - '0';
		}
	}
	
	bfs();

	//for (int i = 0; i < 2; i++) {
	//	for (int j = 1; j <= N; j++) {
	//		for (int k = 1; k <= M; k++) {
	//			cout << dis[j][k][i] << ' ';
	//		}
	//		cout << '\n';
	//	}
	//	cout << '\n'; cout << '\n';
	//}
	//
	return 0;
}