백준 그래프 2206 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

위 문제는 기존의 그래프 문제들과는 많이 다른 유형이었다. 큐나 배열에 해당 좌표뿐만 아니라 벽을 부술 수 있는지와 이전에 벽을 부술 수 있는지를 체크해야했다. 그래서 아래 코드에는 1이면 벽을 부술 수 있다. 0이면 벽을 부술 수 없다로 코드를 작성하였습니다. 

 

벽을 만난적이 있는지 확인하기 위해 canVisit이라는 변수를 만들어서 확인했습니다.

 

일반적인 길(0)이라면 벽을 만난적이 있는지 없는지에 따라 canVisit으로 확인하여 만나적 있다면 [y][x][0]에 값을 저장하고 있다면 [y][x][1]에 값을 저장합니다. 

 

이전에 벽을 부순적이 있다면 새로운 벽을 만날시에 당연히 부술 수 없습니다. canVisit이 0이면 밑에 map이 1일때 조건문에 들어갈 수 없습니다. 그리고 처음 벽을 부순다고하면 큐에 canVisit에 0 값을 저장하여 이미 벽을 부순 경험이 있다고 저장합니다.  

 

그리고 이전에는 map의 값을 변경하여 방문했던 좌표에 방문을 하지 못하게 만들었는데 아래에서는 map의 값을 변경시킬 수 없어 checked를 통해 방문한적이 있는지 없는지 체크했습니다.

 

부순 경우 및 부술 수 없는 경우 모든 경로를 확인하면 0을 제외한 더 작은 값을 출력하면 됩니다. 

 

#include <cstdio>
#include <queue>
#include <utility>
#include <algorithm>

using namespace std;

queue <pair<pair<int, int> ,int> > qu;

int map[1002][1002];
int distanceArray[1002][1002][3];
int checked[1002][1002][3]; // 1 벽을 부술 수 있다. 0 벽을 부술 수 없다. 

int xPos[4] = {1, 0, -1, 0};
int yPos[4] = {0, 1, 0, -1};
int destinationCount = 0;

int N, M;

void input();

void bfs();

int main(){
	input();

	bfs();

	if(!distanceArray[N][M][0] && !distanceArray[N][M][1] ){
		printf("-1");
		return 0;
	}

	if(distanceArray[N][M][0] == 0){
		printf("%d", distanceArray[N][M][1]);
	}else if(distanceArray[N][M][1] == 0){
		printf("%d", distanceArray[N][M][0]);
	}else if(distanceArray[N][M][0] < distanceArray[N][M][1]){
		printf("%d", distanceArray[N][M][0]);
	}else{
		printf("%d", distanceArray[N][M][1]);
	}
}

void input(){
	scanf("%d %d", &N, &M);
	for(int y =1; y <= N; y++)
		for(int x = 1; x <= M; x++)
			scanf("%1d", &map[y][x]);

	qu.push(make_pair(make_pair(1, 1), 1));
}


void bfs(){
	distanceArray[1][1][0] = 1;
	distanceArray[1][1][1] = 1;

	checked[1][1][0] = 1;
	checked[1][1][1] = 1;

	while(!qu.empty()){
		pair <int, int> point = qu.front().first;
		int canVisit = qu.front().second;
		qu.pop();

		for(int i = 0; i < 4; i++){
			int ay = point.first+yPos[i]; 
			int ax = point.second+xPos[i];
			if(ay >=1 && ax >=1 && ay <= N && ax <= M){
				if(map[ay][ax] == 0 && checked[ay][ax][canVisit] == 0){
					checked[ay][ax][canVisit] = 1;
					distanceArray[ay][ax][canVisit] = distanceArray[point.first][point.second][canVisit]+1;
					qu.push(make_pair(make_pair(ay,ax), canVisit));
				}else if(map[ay][ax] == 1 && canVisit && checked[ay][ax][0] == 0){
					checked[ay][ax][0] = 1;
					distanceArray[ay][ax][0] = distanceArray[point.first][point.second][canVisit]+1;
					qu.push(make_pair(make_pair(ay,ax), 0));
				}
			
			}	
		}
	}
}