20) 백준 2206 - 벽 부수고 이동하기

2206번: 벽 부수고 이동하기 (acmicpc.net)

2206번: 벽 부수고 이동하기

---

초반에는 벽 부수는 것 때문에 난감했던 문제

#include <bits/stdc++.h>

using namespace std;

int x_p[4] = {0, 0, 1, -1};
int y_p[4] = {1, -1, 0, 0};
char maze[1000][1000] = {0, };

// first : length, second : wall_check - 한번도 안지났으면 0, 부쉈으면 1 
pair<int, int> check[1000][1000];

int main(void) {
	fill_n(&check[0][0], 1000000, make_pair(1000001, 0));
	
	int N, M, x, y;
	cin >> N >> M;
	
	for(int i = 0; i < N; i++) {
		for(int j = 0; j < M; j++) {
			cin >> maze[i][j];
		}
	}
	
	// x, y
	queue<pair<int, int> > q;
	q.push(make_pair(0, 0));
	
	check[0][0].first = 1;
	check[0][0].second = 0;
	
	while(!q.empty()) {
		x = q.front().first;
		y = q.front().second;
		q.pop();
		
		if(x == N-1 && y == M-1) {
			break;
		} 
		
		for(int i = 0; i < 4; i++) {
			int tmpX = x + x_p[i];
			int tmpY = y + y_p[i];
			if(tmpX >= 0 && tmpY >= 0 && tmpX < N && tmpY < M) {
				if(check[tmpX][tmpY].first > check[x][y].first + 1) {
					if(check[x][y].second == 0) {
						if(maze[tmpX][tmpY] == '0') {
							q.push(make_pair(tmpX, tmpY));
							check[tmpX][tmpY].first = check[x][y].first + 1;
							check[tmpX][tmpY].second = 0;
						}
						else {
							q.push(make_pair(tmpX, tmpY));
							check[tmpX][tmpY].first = check[x][y].first + 1;
							check[tmpX][tmpY].second = 1;
						}
					}
					else {
						if(maze[tmpX][tmpY] == '0') {
							q.push(make_pair(tmpX, tmpY));
							check[tmpX][tmpY].first = check[x][y].first +1;
							check[tmpX][tmpY].second = 1;
						}
					}
				}
				else {
					if(check[x][y].second == 0 && check[tmpX][tmpY].second == 1) {
						if(maze[tmpX][tmpY] == '0') {
							q.push(make_pair(tmpX, tmpY));
							check[tmpX][tmpY].first = check[x][y].first + 1;
							check[tmpX][tmpY].second = 0;
						}
						else {
							q.push(make_pair(tmpX, tmpY));
							check[tmpX][tmpY].first = check[x][y].first + 1;
							check[tmpX][tmpY].second = 1;
						}
					}
				}
			}
		}
	}
	if(x == N-1 && y == M-1) {
		cout << check[x][y].first << endl;
	}
	else {
		cout << "-1" << endl;
	}
	
	
	return 0;
}

최단 거리를 체크하기 위해서 check 배열을 썼다. 

단순히 카운팅만 하는 것이 아닌 벽을 부쉈는지 안 부쉈는지도 체크를 해줬다.   

pair<int, int> check;

first는 거리 카운팅을 second는 벽을 부쉈는지를 체크했다.

 

처음에는 벽을 부순 것을 체크하고 후처리를 해주지 않았다. (필요 없다고 생각했다.)

그런데 정답을 맞추지 못해서 하나하나 체크해 봤다. 

 

결론은 길이 있음에도 단순히 한번 부순 것이 더 빠르다는 이유로 체크를 하지 않고 그냥 넘어갔다.

 

따라서 후처리를 해줬다.

방법은 다음과 같다.

 

1. check 배열에서 같은 인덱스를 처리할 때 벽인지 아닌지를 먼저 체크

2. 벽이면 1로, 아니면 0으로 재설정을 해주었다.

 

가능했던 이유는 만약 벽 부수고 가는 것이 더 빨랐다면 진작에 도착했을 것이다. 그러면 return 되면서 프로그램 종료.

하지만 도착을 못했을 경우에는 재설정을 통해서 다시 목적지로 이동하는 시도를 해볼 것이다.

 

 

중간에 이거 벽 부수는 것이랑 안 부수는 것이랑 따로 Queue 돌려줘야 하나.. 해서 고민을 많이 했다.