백준 2206 (벽 부수고 이동하기)

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

2206번: 벽 부수고 이동하기

해당 문제는 N by M 크기의 격자판이 주어지고 해당 격자판에서 N , M의 위치까지 최단거리를 찾는 문제이다. 이때 이동시 지켜야할 규칙이 존재한다. 규칙은 다음과 같다.

1. 맵 밖으로 벗어날 수 없다.
2. 맵에는 벽이 존재하며 벽 1개 까지는 뚫고 갈 수 있다.
3. 이동 방향은 위, 아래, 좌, 우측으로 이동이 가능하다.

여기서 핵심은 벽을 최대 1개까지 뚫고 가면서 이동할 때 N, M에 도착하는 최단 시간을 구하는 부분이다.

 

풀이 :

이미 이동한 경로를 체크해줄 visit 배열을 사용하며 이때 visit 배열은 3차원 배열을 사용한다. 3차원 배열을 사용하여 벽을 뚫고 갔을 때 의 경우와 벽을 뚫고 가지 않았을 경우 2가지를 따로 Check 한다.

#include <iostream>
#include <queue>

using namespace std;
// 벽을 뚫은 Node는 wall = 1
// 벽을 뚫은 적 없는 Node는 wall = 0
struct Node{
	int y, x;
	int wall;
	int cnt;
};
int n, m;
int res = 10000000;
int checkY[4] = { 0, 0, +1, -1 };
int checkX[4] = { 1, -1, 0, 0 };
char map[1001][1001];

// visit[dy][dx][0] => 아직 벽을 뚫지 않은 경우
// visit[dy][dx][1] => 벽을 한번 뚫은 경우
int visit[1001][1001][2] = { 0 };

void bfs(){
	queue<Node> qu;
	qu.push({ 1, 1, 0, 1 });
	visit[1][1][0] = 1;

	while (!qu.empty()){
		Node now = qu.front();
		// n m 도착시 현재 cnt 갱신
		if (now.y == n && now.x == m){
			res = now.cnt;
			return;
		}
		for (int i = 0; i < 4; ++i){
			int dy = now.y + checkY[i];
			int dx = now.x + checkX[i];
			if (dy <= 0 || dx <= 0 || dy > n || dx > m)continue;
			// 벽을 뚫지 않았으며 아직 방문한적 없을 경우
			if (now.wall == 0 && visit[dy][dx][0] == 0){
				// 현재 방문하는 곳이 벽일 경우 wall 을 1로 변경하여 push
				// visit[][][1] 째 배열에 벽을 뚫은 경우의 이동 경로를 저장
				if (map[dy][dx] == '1'){
					visit[dy][dx][1] = 1;
					qu.push({ dy, dx, 1, now.cnt + 1 });
				}
				// 현재 방문하는 곳이 벽이 아닐경우 wall 은 0이며 
				// visit[][][0] 째 배열에 벽을 뚫지 않은 경우의 이동 경로 저장
				if (map[dy][dx] == '0'){
					visit[dy][dx][0] = 1;
					qu.push({ dy, dx, 0, now.cnt + 1 });
				}
			}
			// 벽을 이미 한번 뚫은 경우
			if (now.wall == 1){
				// 이동하는 곳이 벽이 아니면서 벽을 뚫은 경우의 이동경로 중 방문한적 없는 경우만 push
				if (map[dy][dx] == '0' && visit[dy][dx][1] == 0){
					visit[dy][dx][1] = 1;
					qu.push({ dy, dx, 1, now.cnt + 1 });
				}
			}
		}
		qu.pop();
	}
	res = -1;
	return;

}


int main(){
	//freopen_s(new FILE*, "tes.text", "r", stdin);
	cin >> n >> m;

	for (int i = 1; i <= n; ++i){
		for (int j = 1; j <= m; ++j){
			cin >> map[i][j];
		}
	}

	bfs();
	cout << res << endl;




}