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

문제링크:https://www.acmicpc.net/problem/2206

2206번: 벽 부수고 이동하기

 

bfs문제입니다.

근데 기존의 bfs와 다른점은 벽을 한번 부수고 갈 수 있다는 점입니다. 

 

처음으로 생각하셔야 할 것은 각 점마다 벽을 뚫고 이동하는 최단경로와 벽을 뚫지 않고 이동하는 최단경로를 고려해주어야 한다는 점입니다. (1)

 

두번째로 생각하셔야 할 것은 최단거리검색이라는 점입니다. 그렇기 때문에 방문한 곳이라면 굳이 다시 방문할 필요가 없다는 것을 인지하셔야 합니다. (이 점은 기존 bfs와 같습니다.) (2)

 

1. 벽이 아니고 현재 방문한적이 없을 때 ( 벽을 뚫고 방문한 것과 벽을 뚫지 않고 도착한 것 두가지를 모두 고려해주어야 합니다. 왜냐하면 이미 벽을 뚫고 도착해서 최단경로값을 표시하는 경우가 있기 때문입니다.)

     1) 큐에 좌표와 벽부수기가능여부를 넣어줍니다.

     2) 최단거리값에 1더해주기 

 

2. 벽이고 뚫을 수 있을 때 (벽을 뚫은 적이 있다면 더이상 벽을 뚫을 수 없고, 뚫은 적이 없을 경우 해당 벽을 뚫고 벽을 뚫은 최단경로에 포함시켜줍니다. )

     1) 큐에 좌표와 불가능을 넣어줍니다.

     2) 벽을 뚫은 최단거리에 기존 벽뚫기 전 최단거리값에 1을 더해 넣어줍니다. 

 

테스트 케이스

8 8
01000100
01010100
01010100
01010100
01010100
01010100
01010100
00010100

 

5 8
01000000
01010000
01010000
01010011
00010010

 

 

정답코드입니다.

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
int n = 0, m = 0;
bool arr[1001][1001] = { 0 }; // 0 1을 저장하는 배열 
int  visited[1001][1001][2] = { 0 }; // 방문거리 
string v; // 문자열로 받고 arr에 다시 넣기위해 쓰는 변수 
queue<int> que[3]; //y,x,벽가능여부 

int x_ar[4] = { 1,0,-1, 0};
int y_ar[4] = { 0,1,0,-1 };

void bfs() {
	visited[1][1][1] = 1;
		
	que[0].push(1); //y
	que[1].push(1); //x
	que[2].push(1); // 벽뚫기 가능

	while (que[0].empty() != true) { // 큐가 빌때 까지 반복합니다. 
		int yy = que[0].front();
		int xx = que[1].front();
		int talent = que[2].front(); //1이면  벽뚫기 가능
		que[0].pop();
		que[1].pop();
		que[2].pop(); 

		for (int i = 0; i < 4; i++) {
			int y = yy + y_ar[i];
			int x = xx + x_ar[i];
			if (y >= 1 && y <= n && x >= 1 && x <= m) { // 배열범위에 포함되는지 확인 
				if (arr[y][x] == 0 && visited[y][x][talent] == 0) {//벽이 아니고 방문한 적 없을때
					que[0].push(y); //y
					que[1].push(x); //x
					que[2].push(talent); // 벽뚫기 가능
					visited[y][x][talent] = visited[yy][xx][talent] + 1;
				}
				else if (arr[y][x] == 1 && talent == 1) { //벽이고 아직 안 뚫었을때 
					visited[y][x][talent - 1] =  visited[yy][xx][talent] + 1;
					que[0].push(y); //y
					que[1].push(x); //x
					que[2].push(0); //벽을 더이상 뚫지 못한다. 
				}
			}

		}


	}

}

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> v;
		for (int j = 1; j <= m; j++)
			if (v[j-1] == '1')
				arr[i][j] = 1;
	}


	bfs(); 
	
	
	if (visited[n][m][1] == 0 && visited[n][m][0] == 0)
		cout << -1 << '\n';
	else if(visited[n][m][1] != 0 && visited[n][m][0] != 0)
		cout << min(visited[n][m][0], visited[n][m][1]) << '\n';
	else
		if(visited[n][m][1] == 0)
			cout << visited[n][m][0] << '\n';
		else
			cout << visited[n][m][1] << '\n';
}