[백준 2206번] 벽 부수고 이동하기

[백준 2206번] 벽 부수고 이동하기

www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

 

 문제

 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다.

 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동하여도 된다.

 한 칸에서 이동할 수 있는 칸은 상하좌우로 인접한 칸이다.

 맵이 주어졌을 때, 최단 경로를 구해 내는 프로그램을 작성하시오.

 

 입력

 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.

 

 출력

 첫째 줄에 최단 거리를 출력한다. 불가능할 때는 -1을 출력한다.

 

 

 풀이

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <string>
using namespace std;

int N, M;
int arr[1002][1002];
vector<pair<int, int>> v;
int dx[4]={-1, 1, 0, 0};
int dy[4]={0, 0, -1, 1};

int bfs(){
	queue<pair<pair<int, int>, pair<int, bool>>> q;
	q.push(make_pair(make_pair(1, 1), make_pair(1, false)));
	pair<bool, bool> check[1002][1002] = {make_pair(false, false), };
	check[1][1] = make_pair(true, false);
	
	while(!q.empty()){
		int a = q.front().first.first;
		int b = q.front().first.second;
		int k = q.front().second.first;
		bool o = q.front().second.second;
		q.pop();
		
		for(int i=0;i<4;i++){
			int x = a + dx[i];
			int y = b + dy[i];
			
			if(x == N && y == M) return k+1;
			if(!check[x][y].first && arr[x][y]==0){
				q.push(make_pair(make_pair(x, y), make_pair(k+1, o)));
				check[x][y] = make_pair(true, o);
			}
			else if(check[x][y].first && check[x][y].second && arr[x][y]==0 && !o){
				q.push(make_pair(make_pair(x, y), make_pair(k+1, o)));
				check[x][y] = make_pair(true, o);
			}
			else if(!check[x][y].first && arr[x][y]==1 && !o){
				q.push(make_pair(make_pair(x, y), make_pair(k+1, true)));
				check[x][y] = make_pair(true, true);
			}
		}
	}
	
	return -1;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	string s;
	cin >> N >> M;
	for(int i=1;i<=N;i++){
		cin >> s;
		for(int j=1;j<=M;j++){
			arr[i][j] = s[j-1] - '0';
			if(arr[i][j] == 1){
				v.push_back(make_pair(i, j));
			}
		}
	}
	for(int i=0;i<=M+1;i++){
		arr[0][i] = -1;
		arr[N+1][i] = -1;
	}
	for(int i=0;i<=N+1;i++){
		arr[i][0] = -1;
		arr[i][M+1] = -1;
	}
	
	if(N==1 && M==1) cout << 1;
	else cout << bfs();
	return 0;
}

 bfs로 유명한 벽 부수고 이동하기 문제를 드디어 풀어보았다. 한 3일 쉬었더니 다시 감이 떨어진건지 8트라이만에 겨우 풀었다. 문제를 보자마자 연구소 문제처럼 벽 지우고 bfs 돌리고 벽 세우고 하는 방식으로 구현을 했다가 시간초과로 뚝배기가 깨졌다. 이렇게 구현하면 O(NMNM)으로 N,M의 범위가 1000까지라서 당연히 시간초과였다. 그래서 알아보니 bfs 한번 돌리면서 벽을 부수며 거리를 체크하는 O(NM)의 방법이 있었다. 이해하자마자 바로 코드를 수정했는데, 원래 코드를 최대한 가져가고 싶은 마음에 쉽지가 않았다.

 

 1. 벽이던 길이던 이동 후 방문 체크

 2. 벽이면 부쉈다는 표식을 가지고 큐로 들어감

 3. 방문한 곳인데 벽을 부수고 방문한 기록이면 이동 가능

 

6 4
0000
1110
1110
0000
0111
0000

 

 3번을 해결하는데 시간이 꽤나 걸린 것 같다. 위의 예시를 가지고 설명하면 이해가 빠른데 방문 체크만 하다보면 위 예시에서 (1, 4)에서 (2,4)로 가는 길과 (2, 3)에서 (2,4)로 가는 길에서 문제가 생긴다. 하여튼 메모리 초과도 나보고 우여곡절이 많긴 했지만 결국 해결해서 다행이다. 코드가 더러운 것 같아 아쉽긴하다.