[백준 / C++] 2206번 벽 부수고 이동하기 - (1) , BFS

백준 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을 출력한다.

예제 입력 1 

6 4
0100
1110
1000
0000
0111
0000

예제 출력 1 

15

 

---

 

벽 부수고 이동하기 풀이

 

이 문제를 보았을 때, 상하좌우로 이동 + 최단거리 ? => BFS 라고 생각했다.

하지만, 일반적인 BFS 문제가 아니라 한 가지 예외 상황이 있었다. 그 예외는 바로 갈 수 없는 벽 (1) 일 때 한 번은 벽을 깨고 갈 수 있다는 조건이었다.

 

그래서, 처음 문제를 접근할 때는 모든 1을 queue에 모은 다음에 queue에 들어가있는 1을 0으로 처리하고, BFS 돌리고 끝나면 다음 queue에 들어있는 1을 0으로 바꾸고를 반복했다. 이렇게 했을 때 Test case나, 반례들은 통과했지만 시간초과가 떴다... 

일단 n,m이 최대 1000이기 때문에 1이 출발 지점과 도착지점을 제외했을 때 모두 1이라면, bfs를 998번을 돌아야한다...ㅋㅋ

 

이 방법을 포기하고 다른 방법을 찾던 중, bfs 인자를 3개로 받아 (X, Y, removed) 이렇게 받았다. 여기서 removed는 0이면 아직 한번도 벽을 깨지 않았다 표시고, 1이면 이미 벽을 한번 깼다라는 표시이다. 이렇게 경우를 한번 더 쪼갠 뒤, dist(거리) 거리도 0일 때와 1일 때를 분리해서 구하면 이 문제를 해결할 수 있다. 

 

BFS 부분 코드

void one_delete() {

	queue<tuple<int, int, int>> q;
	q.push({ 1,1,0 });
	dist[1][1][0] = 1;
	
	dist[n][m][0] = MAX;
	dist[n][m][1] = MAX;

	while (!q.empty()) {
		int x = get<0>(q.front());
		int y = get<1>(q.front());
		int removed = get<2>(q.front());

		q.pop();

		for (int i = 0; i < 4; i++) {
			int dxx = x + dx[i];
			int dyy = y + dy[i];

			if (dxx > 0 && dyy > 0 && dxx <= n && dyy <= m) {
				if (real_num[dxx][dyy] == 0 && removed == 0 && check[dxx][dyy][0] == 0) {
					q.push({ dxx,dyy,0 });
					check[dxx][dyy][0] = 1;
					dist[dxx][dyy][0] = dist[x][y][0] + 1;
				}
				else if (real_num[dxx][dyy] == 0 && removed == 1 && check[dxx][dyy][1] == 0) {
					q.push({ dxx,dyy,1 });
					check[dxx][dyy][1] = 1;
					dist[dxx][dyy][1] = dist[x][y][1] + 1;
				}
				else if (real_num[dxx][dyy] == 1 && removed == 0 && check[dxx][dyy][1] == 0) {
					q.push({ dxx,dyy, 1 });
					check[dxx][dyy][1] = 1;
					dist[dxx][dyy][1] = dist[x][y][0] + 1;
				}
			}
		}
	}


	MAX = min(dist[n][m][0], dist[n][m][1]);

	return;
}

 

---

2206 벽 부수고 이동하기 전체 코드 

#include<iostream>
#include<queue>
#include <string>
#include<tuple>
#include <climits>

using namespace std;

int real_num[1001][1001] = { 0 };
queue<pair<int,int>> one_check;
int n, m;
int dx[4] = { 1, 0 ,-1, 0 };
int dy[4] = { 0, 1 , 0 ,-1 };
int dist[1001][1001][2] = { 0 };
int check[1001][1001][2] = { 0 };
int MAX = 999999;
int fake_num[1001][1001] = { 0 };

void one_delete() {

	queue<tuple<int, int, int>> q;
	q.push({ 1,1,0 });
	dist[1][1][0] = 1;
	
	dist[n][m][0] = MAX;
	dist[n][m][1] = MAX;

	while (!q.empty()) {
		int x = get<0>(q.front());
		int y = get<1>(q.front());
		int removed = get<2>(q.front());

		q.pop();

		for (int i = 0; i < 4; i++) {
			int dxx = x + dx[i];
			int dyy = y + dy[i];

			if (dxx > 0 && dyy > 0 && dxx <= n && dyy <= m) {
				if (real_num[dxx][dyy] == 0 && removed == 0 && check[dxx][dyy][0] == 0) {
					q.push({ dxx,dyy,0 });
					check[dxx][dyy][0] = 1;
					dist[dxx][dyy][0] = dist[x][y][0] + 1;
				}
				else if (real_num[dxx][dyy] == 0 && removed == 1 && check[dxx][dyy][1] == 0) {
					q.push({ dxx,dyy,1 });
					check[dxx][dyy][1] = 1;
					dist[dxx][dyy][1] = dist[x][y][1] + 1;
				}
				else if (real_num[dxx][dyy] == 1 && removed == 0 && check[dxx][dyy][1] == 0) {
					q.push({ dxx,dyy, 1 });
					check[dxx][dyy][1] = 1;
					dist[dxx][dyy][1] = dist[x][y][0] + 1;
				}
			}
		}
	}


	MAX = min(dist[n][m][0], dist[n][m][1]);

	return;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> m;

	for (int i = 1; i <= n; i++) {

		string ex;
		cin >> ex;


		for (int j = 1; j <= m; j++) {

			int exx = ex[j - 1];
			real_num[i][j] = exx - 48;
			
		}
	}
	if (n == 1 && m == 1) {
		MAX = 1;
		cout << MAX;
		return 0;
	}

	one_delete();
	
	if (MAX == 999999) {
		cout << -1;
		return 0;
	}
	else {
		cout << MAX;
		return 0;
	}
}