목수의 미로 탈출 (BFS)

문제

---

아래와 같이 이동할 수 있는 길, 그리고 이동할 수 없는 벽으로 이루어진 크기 N x M 의 지도가 주어진다. 이 때, (N-1, 0) 에서 출발하여 (0, M-1) 까지 도착하는 최단거리를 찾으려 한다. 그런데 목수는 도끼 하나를 갖고 있으며, 이 도끼를 이용하여 벽을 깨부술 수 있다. 하지만 이 도끼는 내구성이 그렇게 좋지 않기 때문에, 벽을 최대 1개밖에 깰 수 없다. 목수가 출발점에서 도착점까지 이동하기 위한 최단거리를 출력하는 프로그램을 작성하시오. 물론, 벽은 최대 1개까지 깰 수 있다. 아래 예제의 경우 ‘X’ 로 표시된 벽을 깰 경우 거리 18만에 출발점에서 도착점으로 이동할 수 있다.

 

입력

---

첫째 줄에 지도의 세로 길이 N과 지도의 가로 길이 M이 주어진다. ( 1 ≤ N, M ≤ 1,000 ) 둘째 줄부터 지도의 정보가 주어진다. 0은 이동할 수 있는 부분, 1은 이동할 수 없는 부분을 나타낸다.

 

출력

---

목수가 (N-1, 0) 에서 출발하여 (0, M-1) 까지 이동하는 데 필요한 최단거리를 출력한다. 목수는 미로를 항상 탈출할 수 있다고 가정한다.

 

예제 입력

10 10
0 0 0 0 0 0 1 1 0 0
0 1 1 1 0 0 1 0 1 0 
0 1 1 1 0 0 1 0 1 0
0 0 0 0 0 0 0 0 1 0
0 0 1 1 1 1 0 0 1 0
0 0 0 0 0 0 1 1 0 0
0 0 1 1 1 0 1 1 0 0
0 0 1 1 1 0 0 0 0 0 
0 0 0 0 0 1 1 1 0 0
0 0 0 0 0 0 0 1 0 0

예제 출력

18

 

예제 입력

10 10
0 0 0 0 0 0 1 1 0 0
0 1 1 1 0 0 1 1 1 0
0 1 1 1 0 0 1 1 1 0
0 0 0 0 0 0 0 1 1 0
0 0 1 1 1 1 0 1 1 0
0 0 0 0 0 0 1 1 0 0
0 0 1 1 1 0 1 1 0 0
0 0 1 1 1 0 0 1 0 0
0 0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 0 1 0 0

예제 출력

22

---

풀이)

벽을 한번만 깰 수 있으니
1) 시작점에서 도착지까지 루트
2) 도착지에서 시작점까지 루트

이 두가지를 BFS로 cost1, cost2 이차원배열에 저장합니다.

 

그러면 벽을 한번만 깨거나 벽을 안깨고 도착할 수 있는 최단거리를 계산할 수 있겠죠?!

 

 

---

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
#include <utility>

using namespace std;

const int MAX = 1010;
bool visited[MAX][MAX];	//	방문처리
int map[MAX][MAX], c1[MAX][MAX], c2[MAX][MAX];	//	입력배열, cost1, cost2 배열
int dx[4] = { -1,0,0,1 }, dy[4] = { 0,-1,1,0 };	//	상하좌우
int n, m, result;
queue<pair<int, int>> q;
pair<int, int> p;

void BFS(int x, int y, int cost[MAX][MAX])
{
	visited[x][y] = true;
	p.first = x, p.second = y;
	q.push(p);

	while (!q.empty())
	{
		pair<int, int> current = q.front();
		q.pop();

		int nx = current.first, ny = current.second;

		for (int i = 0; i < 4; i++)
		{
			int xx = nx + dx[i], yy = ny + dy[i];
			if (1 <= xx && xx <= n && 1 <= yy & yy <= m && !visited[xx][yy])
			{
				visited[xx][yy] = true;
				cost[xx][yy] = cost[nx][ny] + 1;

				if (!map[xx][yy])
				{
					pair<int, int> temp;
					temp.first = xx, temp.second = yy;
					q.push(temp);
				}
			}
		}
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) cin >> map[i][j];

	BFS(n, 1, c1);
	memset(visited, 0, sizeof(visited));
	BFS(1, m, c2);

	result = MAX*MAX;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (c1[i][j] > 0 && c2[i][j] > 0)
				result = min(result, c1[i][j] + c2[i][j]);
		}
	}
	
	cout << result;

	return 0;
}