[BFS, 난이도 상] 백준 2206번 벽 부수고 이동하기

정답율 23%의 다소 까다로운편인 문제이다.

아무리 고민해도 해결하지 못한 비슷한 유형의 문제가 있었다.

그 문제는 백준 13460번의 구슬 탈출2 이였다.

주어진 예제는 다 돌아가는데.. 반례가 생기고 그 반례까지 돌아가게 하니 또 다른 반례가 생기고...

나 자신과의 혈전이었다.

 

 

구슬 탈출 2의 해결법이 정말 궁금했던 나는 Google Chance를 썼다.

이 유형의 문제는 구조체 와 모든 방문경우 를 다뤄야 한다는 사실을 깨닫고

내가 깨달은 해당 유형의 문제 풀이법을 4줄 요약해보았다.

 

•  한 map 안에 여러 물체가 동시에 움직여야 하는 경우 구조체 이용
•  2개 이상의 물체가 겹칠 수 없는 경우의 처리 -> 겹침의 여부에 상관없이 일단 논리적으로 모두 이동시켜놓은 후에 조건에 맞게 2차 처리 수행
•  노드에 좌표 정보 외에 특정 정보가 있는 경우 구조체 이용
•  좌표 정보 외에 특정 정보가 있는 경우 그 특정 정보까지 포함한 방문 여부 배열 이용

 

이 내가 쓴 요약을 참고하여 정답율이 2% 더 낮은 벽 부수고 이동하기 문제에 적용시켜보았다.

해결 시간은... 상당히 단축한 30분... 이 문제의 해답은 구조체, 특정 정보까지 포함한 방문 여부 배열 이용 이었다.

 

이 문제에 4줄 요약을 이렇게 적용시켰다.

이 문제 같은 경우에는 벽을 최대 한 번 부수고 목적지에 도달할 수 있다.

4줄 요약중 3번 째줄에 있는 좌표 정보 외의 특정 정보는 이 문제에선 현재까지 벽을 부순 횟수(0 or 1) 에 해당된다.

이로써 구조체를 써야 겠다는 판단,

4줄 요약의 4번째 줄 처럼 특정 정보까지 포함한 방문 여부 배열이 필요 하다는 판단을 했다.

즉, 단순 좌표 배열인 visited[1001][1001]가 아닌 visited[2][1001][1001] 이라는 3차원 배열을 사용해야 된다는 결론에 이르렀다. 현재까지 벽을 부순 횟수는 0아니면 1이기 때문에 [2]를 추가한 것이다. 

BFS상 같은 좌표에 있더라도 현재 그 노드가 벽을 한 번 부순 상태인 노드인건지 한 번도 부수지 않은 노드인건지 방문 처리를 다르게 해주는 것이다.

상하좌우 벽을 탐색해서 벽을 마주쳤는데, 자신이 벽을 한 번 부순 노드라면 큐에 넣지 않고 한 번도 부수지 않은 노드라면 벽을 부순 횟수를 1로 증가시키고 탐색한 좌표를 큐에 넣는 것이다. 이렇게 하면 문제가 해결된다.

 

 

#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <stack>
#include <string>
using namespace std;
struct point {
	int depth;
	bool crushed;
	int px, py;
};
int map[1001][1001];
int time[1001][1001];
bool visited[2][1001][1001]; //깨부순횟수,x,y좌표
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,-1,1 };
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,m;
	cin >> n >> m;
	queue<point> q;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < m; j++) {
			map[i][j] = s[j] - '0';
		}
	}
	q.push(point{1,false, 0, 0 });
	visited[0][0][0] = true;
	while (!q.empty()) {
		point _point = q.front();
		q.pop();
		if (_point.px == n - 1 && _point.py == m - 1) {
			cout << _point.depth;
			return 0;
		}
		for (int i = 0; i < 4; i++) {
			if (_point.px + dx[i] < 0 || _point.px + dx[i] >= n || _point.py + dy[i] < 0 || _point.py + dy[i] >= m) continue;

			if (_point.crushed == false && !visited[0][_point.px + dx[i]][_point.py + dy[i]] && map[_point.px + dx[i]][_point.py + dy[i]]==0) { //부순적이 없고 다음칸이 빈칸일 경우
				q.push(point{_point.depth+1,false,_point.px + dx[i],_point.py + dy[i] });
				visited[0][_point.px + dx[i]][_point.py + dy[i]] = true;
			}
			else if (_point.crushed == false && !visited[1][_point.px + dx[i]][_point.py + dy[i]] && map[_point.px + dx[i]][_point.py + dy[i]] == 1) { //부순적이 없고 다음칸이 벽일 경우
				q.push(point{_point.depth + 1, true,_point.px + dx[i],_point.py + dy[i] });
				visited[1][_point.px + dx[i]][_point.py + dy[i]] = true;
			}
			else if (_point.crushed == true && !visited[1][_point.px + dx[i]][_point.py + dy[i]] && map[_point.px + dx[i]][_point.py + dy[i]] == 0) { //한번 부쉈고 다음칸이 빈칸일 경우
				q.push(point{_point.depth + 1, true,_point.px + dx[i],_point.py + dy[i] });
				visited[1][_point.px + dx[i]][_point.py + dy[i]] = true;
			}
		}
	}
	cout << "-1";
}