💡 너비 우선 탐색/그래프 이론/그래프 탐색
Memory 11572KB Time 296ms Code Length 1178B
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
#include<stdio.h>
#include<queue>
using namespace std;
struct lc {
int y;
int x;
int cnt;
};
int n, m;
int map[1001][1001];
int dy[] = { -1, 1, 0, 0 };
int dx[] = { 0, 0, -1, 1 };
int IsThereRaw() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 0) {
return 1;
}
}
}
return 0;
}
int main() {
scanf("%d %d", &m, &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf(" %d", &map[i][j]);
}
}
queue<lc> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 1) {
q.push({ i,j,0});
}
}
}
int result = -1;
int cnt_time = -1;
while (!q.empty()) {
lc tmp = q.front(); q.pop();
if (cnt_time != tmp.cnt) {
cnt_time = tmp.cnt;
if (!IsThereRaw()) {
// 비어있는곳이 없다는것을 확인하면 result 갱신.
result = cnt_time;
break;
}
}
for (int i = 0; i < 4; i++) {
int ny = tmp.y + dy[i];
int nx = tmp.x + dx[i];
if (ny >= n || nx >= m || ny < 0 || nx < 0) continue;
if (map[ny][nx] == 1 || map[ny][nx] == -1) continue;
map[ny][nx] = 1;
q.push({ ny, nx, tmp.cnt + 1 });
}
}
printf("%d\n", result);
}
이 코드는 주어진 2차원 배열에서 익은 토마토(1)가 있는 위치부터 시작하여 상하좌우로 익지 않은 토마토(0)를 익히는 과정을 시뮬레이션하는 BFS(너비 우선 탐색) 알고리즘을 구현한 것이다.
입력으로 주어지는 n과 m은 각각 배열의 행과 열의 크기를 나타낸다.
IsThereRaw 함수는 배열에 익지 않은 토마토(0)가 남아있는지 확인하는 함수이다.
main 함수에서는 배열을 입력받고, 익은 토마토의 위치를 큐에 넣는다.
큐가 비어있지 않은 동안, 큐에서 토마토를 꺼내면서 상하좌우로 인접한 익지 않은 토마토를 익히는 과정을 반복한다.
cnt_time을 통해 시간을 측정하고, IsThereRaw 함수를 통해 익지 않은 토마토가 더 이상 남아있지 않으면 결과를 갱신하고 종료한다.
즉, 이 코드는 익은 토마토로부터 시작하여 인접한 익지 않은 토마토를 익히는 과정을 BFS로 구현하고, 모든 토마토가 익는데 걸리는 시간을 출력하는 코드이다.
