💡 너비 우선 탐색/그래프 이론/그래프 탐색
Memory 10028KB Time 688ms Code Length 2243B
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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <stdio.h>
#include <string.h>
#include <queue>
// # 벽, . 지나갈수 있는 공간, J 지훈위치, F 불이난 공간.
using namespace std;
int r, c;
char map[1000][1001];
int visited[1000][1000];
int fire_visited[1000][1000];
const int dy[] = { -1, 1, 0, 0 };
const int dx[] = { 0, 0 , -1, 1};
struct info {
int Jy, Jx;
int cnt;
};
int main() {
scanf("%d %d", &r, &c);
for (int i = 0; i < r; i++) {
scanf(" %s", map[i]);
}
queue<info> q;
queue<info> next_q;
info start;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (map[i][j] == 'J') {
start.Jy = i;
start.Jx = j;
visited[i][j] = 1;
}
}
}
start.cnt = 0;
q.push(start);
int flag = 0;
int result;
while (!q.empty()) {
if (flag == 1) break;
// 불의 확산
queue<pair<int, int>> fire;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c; j++) {
if (fire_visited[i][j] == 1) continue; // queue에 추가했던 불 위치는 이미 번졌기 때문에 체크 필요 x
if (map[i][j] == 'F') {
fire.push({ i,j });
fire_visited[i][j] = 1;
}
}
}
while (!fire.empty()) {
pair<int, int> fire_loc;
fire_loc = fire.front(); fire.pop();
for (int i = 0; i < 4; i++) {
int ny = fire_loc.first + dy[i];
int nx = fire_loc.second + dx[i];
if (ny >= r || nx >= c || ny < 0 || nx < 0) continue;
if (map[ny][nx] == '#') continue;
map[ny][nx] = 'F';
}
}
while (!q.empty()) {
// 지훈의 이동 가능 위치 queue에 저장
info tmp = q.front(); q.pop();
// 지훈의 위치가 가장자리?? 탈출
if (tmp.Jy == r - 1 || tmp.Jx == c - 1 || tmp.Jy == 0 || tmp.Jx == 0) {
flag = 1;
result = tmp.cnt + 1;
break;
}
for (int i = 0; i < 4; i++) {
int ny = tmp.Jy + dy[i];
int nx = tmp.Jx + dx[i];
if (ny >= r || nx >= c || ny < 0 || nx < 0) continue;
if (map[ny][nx] == '#') continue;
if (map[ny][nx] == 'F')continue;
if (visited[ny][nx] == 1) continue;
visited[ny][nx] = 1;
info next = tmp;
next.cnt++;
next.Jy = ny;
next.Jx = nx;
next_q.push(next);
}
}
q = next_q;
next_q = queue<info>();
}
if (flag == 0) printf("IMPOSSIBLE\n");
else {
printf("%d\n", result);
}
}
이 코드는 불이 퍼지는 속도와 지훈이 이동하는 속도를 시뮬레이션하여, 지훈이가 탈출할 수 있는지 여부를 판단하는 프로그램이다.
먼저 입력으로 받은 지도에서 지훈이의 위치를 찾고, 지훈이가 이동할 수 있는 위치를 큐에 저장한다. 그리고 불이 퍼지는 속도를 시뮬레이션하여 불이 있는 위치를 갱신한다.
그 후, 지훈이가 이동할 수 있는 위치를 확인하고, 이동할 수 있는 경우에는 다음 이동 가능 위치를 큐에 저장한다. 이를 반복하면서 지훈이가 가장자리에 도착하면 탈출 가능한지 판단하고, 결과를 출력한다.
만약 지훈이가 탈출할 수 없는 경우 “IMPOSSIBLE”을 출력하고, 탈출할 수 있는 경우에는 걸린 시간을 출력한다.
