[백준] 2206 - 벽 부수고 이동하기 ( bfs )

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

2206번: 벽 부수고 이동하기

 

2178번 미로탐색 처럼 단순한 bfs문제라 생각해서 bfs로 접근했다.

충돌판정은 break_cnt 에 기록해서 풀었는데.. 틀렸다.

 

[틀린 코드]

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <climits>
#include <algorithm>
#include <cmath>
#include <utility>

typedef std::tuple<int, int, int, int> PointInfo;
int main(void){
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL);
	
	int n = 0, m = 0;
	int dist = -1;
	
	std::cin >> n >> m;
	int map[n][m] = {{0,}};
	
	for(int i=0; i<n; ++i){
		std::string s;
		std::cin >> s;
		int x = 0;
		for(auto& c : s){
			map[i][x++] = c - '0';
			//std::cout << map[i][x-1] << "\n";
		}
	}
	
	std::queue<PointInfo> q;
	// y,x,count,부순횟수
	q.push(PointInfo(0,0,1,0));
	map[0][0] = 2;
	
	while(!q.empty()){
		//std::cout << "z" << "\n";
		auto& [y,x,count, break_cnt] = q.front();
		q.pop();
		
		if (y == (n-1) && x == (m-1)){
			dist = count;
			break;
		}
		
		if (y-1 >= 0){
			if (map[y-1][x] == 0){
				map[y-1][x] = 2;
				q.push(PointInfo(y-1,x,count+1,break_cnt));
			}else if (map[y-1][x] == 1 && break_cnt == 0){
				q.push(PointInfo(y-1,x,count+1,break_cnt+1));
			}
		}if (x-1 >= 0){
			if (map[y][x-1] == 0){
				map[y][x-1] = 2;
				q.push(PointInfo(y,x-1,count+1,break_cnt));
			}else if (map[y][x-1] == 1 && break_cnt == 0){
				q.push(PointInfo(y,x-1,count+1,break_cnt+1));
			}
		}
		if (y+1 < n){
			if (map[y+1][x] == 0){
				map[y+1][x] = 2;
				q.push(PointInfo(y+1,x,count+1,break_cnt));
			}else if (map[y+1][x] == 1 && break_cnt == 0){
				q.push(PointInfo(y+1,x,count+1,break_cnt+1));
			}
		}
		if (x+1 < m){
			if (map[y][x+1] == 0){
				map[y][x+1] = 2;
				q.push(PointInfo(y,x+1,count+1,break_cnt));
			}else if (map[y][x+1] == 1 && break_cnt == 0){
				q.push(PointInfo(y,x+1,count+1,break_cnt+1));
			}
		}
	}
	
	std::cout << dist << "\n";
	return 0;
}

 

생각하다보니 반례를 찾았는데, 부수고 지나갔을때가 그냥 지나갔을때보다 빠르게 도착한다는 점에서 발생하는 문제였다.

0	0	0	0	0
0	0	0	0	0
1	1	1	0	0
0	0	0	1	1
0	1	0	1	0

 

위 map에서 최단거리는 9가 되어야한다.

하지만 내 틀린코드로 풀면 풀지 못한다. 왜냐하면 (3,3)에서 break_cnt가 1 이된다. 이후 (3,5) 까지 이동했을때 ,

break_cnt 가 1이기 때문에 (4,5)를 뚫지못한다.

또, 다음에 도착한 break_cnt = 0 인 녀석은 (3,5)에 도착하지 못한다.

왜? 바로 break_cnt = 1 인 녀석이 이미 map[3][5] 를 2로 만들었기 때문이다.

 

따라서 나는 새로운 충돌횟수에 따른 visit 배열을 만들어 풀었다.

 

[성공 코드]

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <climits>
#include <algorithm>
#include <cmath>
#include <utility>

typedef std::tuple<int, int, int, int> PointInfo;
int main(void){
	std::ios::sync_with_stdio(false); 
	std::cin.tie(NULL);
	
	int n = 0, m = 0;
	int dist = -1;
	
	std::cin >> n >> m;
	int map[n][m] = {{0,}};
	int visit[n][m][2] = {{{0,}},};
	for(int i=0; i<n; ++i){
		std::string s;
		std::cin >> s;
		int x = 0;
		for(auto& c : s){
			//c = c - '1';
			map[i][x++] = c - '0';//c < 0 ? -c : c;
			visit[i][x-1][0] = visit[i][x-1][1] = 0;
			//std::cout << map[i][x-1];
		}
		//std::cout << "\n";
	}
	
	std::queue<PointInfo> q;
	// y,x,count,부순횟수
	q.push(PointInfo(0,0,1,0));
	visit[0][0][0] = 1;
	
	while(!q.empty()){
		//std::cout << "z" << "\n";
		//std::cout << q.size() << "\n";
		auto& [y,x,count, break_cnt] = q.front();
		q.pop();
		
		//std::cout << visit[y][x][0] << "\n";
		if (y == (n-1) && x == (m-1)){
			dist = count;
			break;
		}
		
		if (y-1 >= 0){
			if (visit[y-1][x][break_cnt] == 0 && map[y-1][x] == 0){
				visit[y-1][x][break_cnt] = 1;
				q.push(PointInfo(y-1,x,count+1,break_cnt));
			}else if (map[y-1][x] == 1 && break_cnt == 0){
				q.push(PointInfo(y-1,x,count+1,break_cnt+1));
				visit[y-1][x][break_cnt+1] = 1;
			}
		}if (x-1 >= 0){
			if (visit[y][x-1][break_cnt] == 0 && map[y][x-1] == 0){
				visit[y][x-1][break_cnt] = 1;
				q.push(PointInfo(y,x-1,count+1,break_cnt));
			}else if (map[y][x-1] == 1 && break_cnt == 0){
				q.push(PointInfo(y,x-1,count+1,break_cnt+1));
				visit[y][x-1][break_cnt+1] = 1;
			}
		}
		if (y+1 < n){
			if (visit[y+1][x][break_cnt] == 0 && map[y+1][x] == 0){
				visit[y+1][x][break_cnt] = 1;
				q.push(PointInfo(y+1,x,count+1,break_cnt));
			}else if (map[y+1][x] == 1 && break_cnt == 0){
				q.push(PointInfo(y+1,x,count+1,break_cnt+1));
				visit[y+1][x][break_cnt+1] = 1;
			}
		}
		if (x+1 < m){
			if (visit[y][x+1][break_cnt] == 0 && map[y][x+1] == 0){
				visit[y][x+1][break_cnt] = 1;
				q.push(PointInfo(y,x+1,count+1,break_cnt));
			}else if (map[y][x+1] == 1 && break_cnt == 0){
				q.push(PointInfo(y,x+1,count+1,break_cnt+1));
				visit[y][x+1][break_cnt] = 1;
			}
		}
	}
	
	std::cout << dist << "\n";
	return 0;
}

 

성공!