백준 16933. 벽 부수고 이동하기 3

알고리즘 중급 문제 중 611 - BFS(연습)

벽 부수고 이동하기 3

4보다 3이 더 어렵다

1. 간단 설명

---

벽 부수고 이동하기 시리즈

낮과 밤이 번갈아가면서 등장하는데, 낮에만 벽을 부술 수 있다

밤에는 시끄러우니까..

벽을 K개 까지 부술 수 있을 때, 최단 경로를 구하는 프로그램 작성

2. 예시

---

예제 1)

1 4 1
0010

낮부터 시작이므로 (0,1) 에 도달했을때 밤이 되고 최단거리가 2가 된다

밤에는 벽을 부술 수 없으므로 한턴 대기해야한다 (최단거리 3)

낮에 (0,2)의 벽을 부수고, 이동한다 (최단거리 4)

(0,3)에 도달했을 때 최단거리는 5가 된다

예제 2)

6 4 2
0100
1110
1000
0000
0111
0000

(0,0)에서 시작 했을 때 낮이므로, (0,1)을 부술 수 있다

(0,3)까지 쭉 이동 후, (3,3)으로 이동한다.

(3,3)에 도달했을 때 낮이므로 (4,3)을 부술 수 있다

(4,3), (5,3)으로 도달하면 최단거리는 9가 된다

3. 알고리즘

---

1. N, M, K를 입력받고, 맵 정보를 입력받는다
2. (0,0)에서 BFS를 돌린다
	2-1. 큐에서 맨 앞을 꺼내 확인한다
	2-2. 만약 좌표가 목표 지점이라면, 현재까지 몇번 움직였는지를 리턴 후 BFS 함수 종료
	2-3. 아니라면, 다음 이동 경로를 체크한다
		2-3-1. 다음 이동 경로(dy, dx)가 맵 밖이라면 패스
		2-3-2. 만약 빈칸이라면
			2-3-2-1. 이 경로를 방문한 적이 있는지 체크한다
				- 만약 첫 방문이라면 최단경로이므로, 기록해두고 큐에 경로 +1 해서 넣는다
		2-3-3. 만약 벽이라면
			2-3-3-1. 벽을 부술 기회가 남아있는지 체크 후 없다면 패스한다
			2-3-3-2. 부술 수 있다면 낮인지 밤인지 체크한다
				2-3-3-2-1. 낮이고, 방문한적 없다면, 벽을 부수고 이동한다
				2-3-3-2-2. 밤인경우, 낮이 올때까지 대기한다

BFS구조가 더럽게 복잡한 문제

구조를 잘못짜면 BFS에 큐 삽입 때문에 메모리초과가 발생한다

그리고, 벽을 만났을 때, 밤인경우 두가지 선택지가 있다

1. 다른칸으로 이동하거나

2. 낮이 올때까지 대기하거나

그런데 낮이 올때까지 기다렸다가 벽을 부수는게, 무조건 돌아가는것보다 더 짧다

0 0 0 0 0
1 1 1 1 0
1 0 0 0 0
0 0 0 0 1 
0 0 0 0 0

다음과 같은 예시가 있을 때, (0, 0)에서 시작해서 (3,4)에 밤에 도달한 상황이라고 가정해보자

큐에는 {3, 4, 7, 1, 1} = (3,2)에 7번 움직인 상황, 벽 한번 부술 수 있고, 밤이다 가 저장되있다

이 때 낮까지 기다렸다가 벽을 부수고 이동하면

낮까지 기다리기 (dist + 1), (4,4) 이동 (dist + 1), 목표 도달해서 총 10번만에 도달 가능하다

그러나 돌아서 가게되면 11번만에 도달 가능하므로, 대기하는게 더 이득이다

이런점을 고려해서 코드를 작성하면 된다

4. 소스코드

---

#include <iostream>
#include <queue>

#define MAX 1001

using namespace std;

int N, M, K;
int map[MAX][MAX];
bool visited[MAX][MAX][10]; // [y][x][낮밤];
int direct[4][2] = { 0,1,1,0,0,-1,-1,0 };

struct Node {
	int y;
	int x;
	int dist;
	int wall_cnt;
	int is_day;
};

void Input() {
	// freopen_s(new FILE*, "input.txt", "r", stdin);
	cin >> N >> M >> K;
	for (int y = 0; y < N; y++) {
		string str; cin >> str;
		for (int x = 0; x < M; x++) {
			map[y][x] = str[x] - '0';
		}
	}
}

int BFS() {
	queue<Node> qu;
	qu.push({ 0,0,1,0,0 }); // (0,0), 처음은 1칸, 벽 부순 회수, 시작은 낮
	visited[0][0][0] = true;

	while (!qu.empty()) {
		auto [y, x, dist, wall_cnt, is_day] = qu.front();
		qu.pop();

		if (y == N - 1 && x == M - 1) {
			return dist;
		}

		for (int t = 0; t < 4; t++) {
			int dy = direct[t][0] + y;
			int dx = direct[t][1] + x;

			if (dy < 0 || dx < 0 || dy >= N || dx >= M) continue; // 경계 체크

			// 1. 빈칸인 경우 : 낮밤 관계없이 이동 가능
			if (map[dy][dx] == 0) { // 방문한 기록이 없다면
				if (visited[dy][dx][wall_cnt] == 0) { // 이 경로를 방문한적 없다면 최단경로이므로 기록해둠
					visited[dy][dx][wall_cnt] = true;
					qu.push({ dy, dx, dist + 1, wall_cnt, 1 - is_day }); // 낮이라면 밤으로, 밤이라면 낮으로 바꿔서 넣는다
				}
			}

			// 2. 벽인경우
			else{
				// 2-1. 낮인경우. 벽을 부술 수 있다면 부수고 이동함
				if (wall_cnt >= K) continue; // 더이상 벽을 부술 수 없다면 패스

				if (is_day == 0) {
					if (visited[dy][dx][wall_cnt + 1] == 0) {
						visited[dy][dx][wall_cnt + 1] = true; // 벽을 부술 기회 한번 소진
						qu.push({ dy, dx, dist + 1, wall_cnt + 1, 1 - is_day });
					}
				}
				// 2-1. 밤인경우. 대기한다
				else {
					qu.push({ y, x, dist + 1, wall_cnt, 1 - is_day }); // dy, dx가 아닌 현재 좌표를 넣어야함
				}
			}			
		}
	}

	return -1;
}

int main() {
	Input();

	cout << BFS();

	return 0;
}

---

if (is_day == 0 && visited[dy][dx][wall_cnt + 1] == 0) {
	visited[dy][dx][wall_cnt + 1] = true; 
	qu.push({ dy, dx, dist + 1, wall_cnt + 1, 1 - is_day });
}
else{
	qu.push({ y, x, dist + 1, wall_cnt, 1 - is_day });
}

if (is_day == 0) {
	if (visited[dy][dx][wall_cnt + 1] == 0) {
		visited[dy][dx][wall_cnt + 1] = true; 
		qu.push({ dy, dx, dist + 1, wall_cnt + 1, 1 - is_day });
	}
}
else {
	qu.push({ y, x, dist + 1, wall_cnt, 1 - is_day });
}

위 두 코드의 차이 때문에 엄청 애먹었다

첫번째 코드를 A∧B -> X, ￢(A∧B) -> Y 라고하면

A와 B가 참일때만 X를 출력하고, 그 외의 경우 Y를 출력한다

두번째 코드는 A∧B -> X, ￢A -> Y로 볼 수 있다

A와 B가 참일때만 X를 출력하고, A가 거짓일 때 Y를 출력한다

직관적으로 잘 와닿지 않을 수 있는데, 예를들면

A와 B라는 전등 스위치가 있을때

첫번째 코드는 A와 B 모두 켜야 전등이 켜지고(AND),

두번째 코드는 A라는 스위치를 끄면 무조건 불이 꺼지고

A를 켜면 B에 따라 불이 ON/OFF 되는 상황이다.

이런 문제를 풀 때 코드의 가독성과 논리 오류 고려해가면서 논리 연산자를 사용해야겠다는 것을 배웠다.