BOJ (C/C++) 2206번: 벽 부수고 이동하기

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

2206번: 벽 부수고 이동하기

---

풀이

최단 거리를 찾는 문제이므로 BFS.

 

벽을 한 번까지는 부술 수 있으므로 현재 상태가 벽을 부술 수 있는 상태인지 아닌지를 구분하여 생각해야 한다.

따라서 BFS를 위해 큐에 넣을 때도 이를 같이 저장해야 하며, 방문 여부와 최솟값을 저장하는 배열 모두 이를 구분해서 저장해야 한다.

 

만약 구분하지 않고 저장한다면, 향후에 벽을 부셔야 도착할 수 있는 상황에서 이미 벽을 부신 게 최소거리가 될 때 도달하지 못 한다고 판단되기 때문

// 해당 경우 예제
5 5
00100
00000
10010
00101
00010
output:-1
answer:9

https://www.acmicpc.net/board/view/97250 <-  출처

 

 

이 문제에 대해 해당 문제 게시판에 어떤 분이 써놓은 글이 있으니 읽어보시면 좋을 것 같습니다.

정답률이 낮은 만큼 게시판에 글도 많으니 반례 찾아보시면서 풀면 풀 수 있을 거에요!

글 읽기 - ★☆★☆★ [필독] 벽 부수고 이동하기 FAQ ★☆★☆★

---

코드

 

(문제에서는 1이 벽으로 설정되었는데, 해당 코드에서는 map에 저장된 값이 0일 때를 벽으로 설정하였습니다)

 

#include <stdio.h>
#include <queue>
using namespace std;

bool map[1001][1001], visited[2][1001][1001];
int Min[2][1001][1001];

auto BFS(int N, int M) {
	int d[4][2] = { {-1,0},{1,0},{0,-1},{0,1} };
	int x, y, nx, ny;
	bool wall;
	queue <pair<pair<int, int>, bool>> Q;

	// init
	Q.push({ {0,0},0 });
	visited[0][0][0] = visited[1][0][0] = Min[0][0][0] = Min[1][0][0] = true;

	// BFS
	while (!Q.empty()) {

		// (x,y) : 현재 위치, wall : 벽을 부술 수 있는 지 (있으면 0, 이미 부셨으면 1)
		x = Q.front().first.first, y = Q.front().first.second, wall = Q.front().second;
		Q.pop();

		for (int i = 0; i < 4; i++) {
			nx = x + d[i][0], ny = y + d[i][1];

			if (nx < 0 || nx > N || ny < 0 || ny > M) continue;


			// 벽일 때
			if (!map[nx][ny]) {

				// 벽을 부술 수 있고, 방문하지 않았을 경우
				if (!wall && !visited[1][nx][ny]) {
					visited[1][nx][ny] = true;
					Min[1][nx][ny] = Min[wall][x][y] + 1;
					Q.push({ {nx,ny},true });
				}
			}

			// 벽이 아닐 때
			else {

				// 방문 여부만 판단
				if (!visited[wall][nx][ny]) {
					visited[wall][nx][ny] = true;
					Min[wall][nx][ny] = Min[wall][x][y] + 1;
					Q.push({ {nx,ny},wall });
				}
			}
		}
	}

	// print
	if (!visited[0][N][M]) {
		if (!visited[1][N][M]) return -1;
		else return Min[1][N][M];
	}
	else {
		if (!visited[1][N][M]) return Min[0][N][M];
		else return Min[0][N][M] < Min[1][N][M] ? Min[0][N][M] : Min[1][N][M];
	}

}
int main() {
	int N, M;
	char s[1003];

	// input
	scanf("%d %d", &N, &M);
	for (int i = 0; i < N; i++) {
		scanf("%s", s);
		for (int j = 0; j < M; j++) {
			if (s[j] == '0') map[i][j] = true;
		}
	}

	printf("%d", BFS(N - 1, M - 1));
	return 0;
}