[백준 2206] 벽 부수고 이동하기

문제

NxM의 맵에서 1은 벽이기 때문에 이동할 수 없고 0은 이동할 수 있다. (1, 1)에서 출발하여 (N, M)까지 이동을 할 때 최소로 이동하는 거리를 구한다. 이때 벽으로인해 이동할 수 없다면 최대 한 번은 벽을 부수고 이동할 수 없다.

벽을 부수고 이동했을 때도 도착지에 가지 못한다면 -1을 출력한다.

 

입력

첫째 줄에 1이상 1000이하의 N과 M을 입력한다.

 

출력

첫째 줄에 최소거리를 출력한다.

---

접근

처음에는 맵을 탐색하다가 벽이 보였을 때 벽을 제거하고 BFS를 하도록 했지만 시간초과가 났다. 그래서 여러번 시도를 해보고 다른 사람들의 풀이를 참고하였다.

BFS를 할 때 3차원 배열로 방문표시와 이동거리를 표시를 한다.

마지막 축은 크기가 2인데 0은 벽을 부수고 이동한거리, 1은 벽을 부수지 않고 이동한 거리를 나타낸다.

즉, 모두 거리를 나타내지만 인덱스 0에는 이전에 벽을 부쉈을 때 이동한거리이며 1은 아직 벽이 나타나지않아 벽을 부수기 전에 이동한 거리이다.

 

이를 활용하여 탐색을 하다가 벽이 나오고 아직 벽이 부수지 않았다면 인덱스 1에 있던 거리+1을 인덱스 0에 넣는다.

 

구현

입력받아야 할 것을 입력받고 BFS를 시작한다.

세 개의 원소를 담는 큐를 선언하고 좌표와 벽을 부쉈는지에 대한 여부를 넣는다. 1은 벽을 부술 수 있다는 표시이다.

그리고 첫 칸에는 벽이 없기 때문에 시작점인(0, 0)의 인덱스 1에 1을 넣고 시작한다.

queue<pair<pair<int, int>, int>> q;
q.push({ {0,0},1 });
dist[0][0][1] = 1;

 

큐가 빌 때까지 진행하며 (cy, cx)에 현재 좌표를 담고 iswall에는 벽을 부수었는지 아닌지를 담는다.

그리고 현재위치가 도착점이라면 최종 거리를 반환한다.

while (!q.empty()) {
		int cy = q.front().first.first;
		int cx = q.front().first.second;
		int isWall = q.front().second;
		q.pop();

		if (cy == N - 1 && cx == M - 1) {
			return dist[cy][cx][isWall];
		}

 

상하좌우를 탐색하여 범위 안에 있을 때 그 다음 조건문을 실행한다.

다음 위치가 벽이고 아직 벽을 부수지 않았을 때 벽을 부수고 진행한다.

iswall에는 1이 담겨있으며 이는 벽을 부수지않고 이동한 거리를 나타낸다. 이 거리에 +1을 하여 벽을 부수고 이동한 거리에 담는다.

그리고 큐에는 다음좌표와 벽을 부쉈다는 의미로 iswall-0을 담는다.

for (int d = 0; d < 4; d++) {
			int ny = cy + dir[d][0];
			int nx = cx + dir[d][1];
			if (check_range(ny, nx)) {
				if (map[ny][nx] == 1 && isWall) {
					dist[ny][nx][isWall-1] = dist[cy][cx][isWall] + 1;
					q.push({ {ny,nx},isWall-1 });
				}

 

그 다음 벽이 아니고 다음위치를 방문하지 않았을 때 방문을 하고 iswall은 현재위치의 상태 그대로 전달한다.

if (map[ny][nx] == 0 &&dist[ny][nx][isWall]==0) {
					dist[ny][nx][isWall] = dist[cy][cx][isWall] + 1;
					q.push({ {ny,nx},isWall });
				}

---

#include <iostream>
#include<algorithm>
#include <vector>
#include<queue>
#include<cmath>
#include<cstring>
using namespace std;

int N, M;
int map[1000][1000];
int answer = 100000000;
const int dir[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
int dist[1000][1000][2];
bool check_range(int y, int x) {
	return(y >= 0 && y < N) && (x >= 0 && x < M);
}

int bfs() {
	queue<pair<pair<int, int>, int>> q;
	q.push({ {0,0},1 });
	dist[0][0][1] = 1;

	while (!q.empty()) {
		int cy = q.front().first.first;
		int cx = q.front().first.second;
		int isWall = q.front().second;
		q.pop();

		if (cy == N - 1 && cx == M - 1) {
			return dist[cy][cx][isWall];
		}
		for (int d = 0; d < 4; d++) {
			int ny = cy + dir[d][0];
			int nx = cx + dir[d][1];
			if (check_range(ny, nx)) {
				if (map[ny][nx] == 1 && isWall) {
					dist[ny][nx][isWall-1] = dist[cy][cx][isWall] + 1;
					q.push({ {ny,nx},isWall-1 });
				}
				if (map[ny][nx] == 0 &&dist[ny][nx][isWall]==0) {
					dist[ny][nx][isWall] = dist[cy][cx][isWall] + 1;
					q.push({ {ny,nx},isWall });
				}
			}
		}
	}
	return -1;
}
int main()
{
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &map[i][j]);
		}
	}

	answer = bfs();
	cout << answer << endl;
}

/*

*/