벽 부수고 이동하기 C++ - 백준 2206

이 글을 포함하고 있는 글

프로그래밍을 하며 느낀점

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

내가 접근하려는 방식은 다음과 같았다.(사실 이렇게 생각하는 힘을 키우는 것도
중요하게 생각한다.)

1. BFS 탐색 시 사방이 막혀 있는 상태에서 벽을 부순다.
2. BFS 탐색 시 queue.size() 가 0일 때 벽을 부순다.
3. 등등

위와 같이 많은 접근들로 코드를 작성했을 때
반례들로 인해 계속 틀렸다.

https://www.acmicpc.net/board/search/all/problem/2206

.
.

이때 답안 코드를 보고 조금 더 본질적이게 생각해보았다.

내가 코드를 작성할 때 주목한 발상이 벽 부수기 부분인데,

이 부분은 사실 내가 접근한 방식대로 복잡하게 접근하는 것보다 더 간단하게

풀리는 풀이가 있다.

내가 이때 놓친 논리는 bfs 알고리즘을 다시 한번 생각하게 하는
생각이었는데,

bfs에서 방문 처리를 한 두 지점 A(A1,A2), B(B1,B2)가 있다고 할 때, 방문 처리를 먼저한 지점이 시작 지점에서 더 가깝다.
+모든 경우를 탐색해야 하지 않을까?

라는 생각이었다.

010001 
010101 
010101 
010101 
010110 
000110 

ans: 21

위의 예제가 있을때 벽을 부순 경우의 경로하고, 부수지 않았을 때의 경로 모두 담아 최단경로를 계산하기로 한다.

따라서 내가 다시 짠 코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int graph[1001][1001];
int visited[1001][1001][2]; //simply stores shorstest path;
int N;                      //ind 0 = just go; ind 1 = crash wall;
int M;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};

void bfs(){
	queue<tuple<int, int, bool>> q; //bool ind 2 = state wall crashed
	q.push({0,0,0});
	
	while(!q.empty()){
		int x=get<0>(q.front());
		int y=get<1>(q.front());
		int crashed=get<2>(q.front());
		
		q.pop();
		
		for(int i=0;i<4;i++){
			int nx=x+dx[i];
			int ny=y+dy[i];
			
			if(0<=nx && nx<N && 0<=ny && ny<M){
				//no wall and no visit
				if(graph[nx][ny]==0 && visited[nx][ny][crashed]==0){
					visited[nx][ny][crashed]=visited[x][y][crashed]+1;
					q.push({nx,ny,crashed});
				}
				//wall and no visit, crash wall
				else if(graph[nx][ny]==1 && visited[nx][ny][crashed]==0){
					if(!crashed){
						visited[nx][ny][1]=visited[x][y][0]+1;
						q.push({nx,ny,1});
					}
				}
			}
		}
	}
}

int main(){
		
	scanf("%d %d", &N, &M);
	
	for(int i=0;i<N;i++){
		for(int j=0;j<M;j++){
			scanf("%1d", &graph[i][j]);
		}
	}
	visited[0][0][0]=1;
	bfs();
	if(visited[N-1][M-1][0]>0){
		if(visited[N-1][M-1][1]>0){
			cout << min(visited[N-1][M-1][1], visited[N-1][M-1][0]);
		}
		else{
			cout << visited[N-1][M-1][0];
		}
	}
	else{
		if(visited[N-1][M-1][1]>0){
			cout << visited[N-1][M-1][1];
		}
		else{
			cout << -1;
		}
	}
}

단순하게 생각해서 bfs 알고리즘을 수행할 때 벽에 관한 bfs도 진행하게 하면 최단 경로를 탐색한다.