JUST WRITE IT. HomeArchivesTagsCategories
백준 3055번 탈출
|AlgorithmBOJ|

#3055. 탈출

Problem

Solution

  • 조건 중에 “물이 찰 예정인 칸에 고슴도치가 움직일 수 없다.“에 집중하였다.
  • 물이 이동할 queue와 고슴도치가 이동할 queue를 따로 두어 탐색을 시작한다.
  • 단, 물이 먼저 이동해야 한다.(위 조건 때문에)
  • 모든 탐색은 BFS로 이루어지며, 물은 이동할 때마다 map을 갱신한다. 고슴도치는 갱신 안한다.
  • 고슴도치가 ‘D’에 도착하지 못 하고 탐색할 지점이 없을 때 -1을 리턴하여 도착할 수 없다는 것을 표시한다.
  • ‘D’에 도착하면 그때 시간을 바로 출력하도록 한다.

1 Try

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <cstdio>
#include <tuple>
#include <queue>
using namespace std;
int R, C;
char map[51][51];
bool visit[50][50];
queue<pair<int, int>> q;
queue<pair<int, int>> water;
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };
void Input() {
	scanf("%d %d", &R, &C);
	for (int i = 0; i < R; ++i) {
		for (int j = 0; j < C; ++j) {
			scanf(" %c", &map[i][j]);
			if (map[i][j] == 'S') { q.push({ i, j }); visit[i][j] = true; }
			else if (map[i][j] == '*') water.push({ i, j });
		}
	}
}
bool isBound(int x, int y) {
	if (x > -1 && y > -1 && x < R && y < C) return true;
	return false;
}
int BFS() {
	int time = 0;
	while (!q.empty()) { // 고슴도치가 탐색할 지점이 없을 때까지 진행
		int w_len = water.size();
		for (int i = 0; i < w_len; ++i) { // 물의 이동
			int water_x, water_y;
			tie(water_x, water_y) = water.front();
			water.pop();  
			for (int dir = 0; dir < 4; ++dir) {
				int d_w_x = water_x + dx[dir];
				int d_w_y = water_y + dy[dir];
				if (isBound(d_w_x, d_w_y)) {
					if (map[d_w_x][d_w_y] == '.' || map[d_w_x][d_w_y] == 'S') {
						map[d_w_x][d_w_y] = '*';
						water.push({ d_w_x, d_w_y });
					}
				}
			}
		}
		int len = q.size();
		for (int i = 0; i < len; ++i) { // 고슴도치 이동
			int x, y;
			tie(x, y) = q.front();
			q.pop();
			if (map[x][y] == 'D') return time; // 목적지 도착하면 시간 리턴
			for (int dir = 0; dir < 4; ++dir) {
				int d_x = x + dx[dir];
				int d_y = y + dy[dir];
				if (isBound(d_x, d_y) && !visit[d_x][d_y]) {
					if (map[d_x][d_y] != 'X' && map[d_x][d_y] != '*') {
						visit[d_x][d_y] = true;
						q.push({ d_x, d_y });
					}
				}
			}
		}
		time++;
	}
	return -1;
}
void Solve() {
	int ans = BFS();
	if (ans == -1) printf("KAKTUS\n");
	else printf("%d\n", ans);
}
int main() {
	Input();
	Solve();
	return 0;
}
Algorithm