💡 너비 우선 탐색/깊이 우선 탐색/그래프 이론/그래프 탐색/구현
Memory 2512KB Time 96ms Code Length 1864B
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
#include<stdio.h>
#include<string.h>
#define MAX 301
int n, m;
int map[MAX][MAX];
int dy[] = {0,0,-1,1};
int dx[] = {-1,1,0,0};
void DFS(int y, int x, int visited[][MAX]) {
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= n || nx >= m || ny < 0 || nx < 0) continue;
if (map[ny][nx] == 0) continue;
if (visited[ny][nx] == 1) continue;
visited[ny][nx] = 1;
DFS(ny, nx, visited);
}
}
int CntIce() { // 현재 전역변수 map의 ICE를 카운팅함.
int visited[MAX][MAX];
memset(visited, 0, sizeof(visited));
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (map[i][j] == 0) continue;
if (visited[i][j] == 1) continue;
visited[i][j] = 1;
cnt++;
DFS(i, j, visited); // 해당 구역 방문처리
if (cnt >= 2) return cnt;
}
}
return cnt; // 0 or 1 반환.
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
scanf(" %d", &map[i][j]);
}
}
int year = 0;
int result = 0;
while (1) {
int numIce = CntIce(); // 빙산 갯수 체크
if (numIce == 0) break; // 0 이면 다녹은것.
else if (numIce == 1) { // 1이면 녹이는 작업 해야함.
year++;
int TMP[MAX][MAX];
memset(TMP, 0, sizeof(TMP));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int cnt = 0;
if (map[i][j] == 0) continue;
for (int k = 0; k < 4; k++) {
int ny = i + dy[k];
int nx = j + dx[k];
if (ny >= n || nx >= m || ny < 0 || nx < 0) continue;
if (map[ny][nx] == 0) cnt++;
}
TMP[i][j] = map[i][j] - cnt;
if (TMP[i][j] < 0) TMP[i][j] = 0;
}
}
memcpy(map, TMP, sizeof(map));
}
else if (numIce == 2) { // 2이면 녹이는 작업 필요 X. 결과만 저장하고 끝내기
result = year;
break;
}
}
printf("%d\n", result);
}
이 코드는 빙산이 주어진 지도에서 녹는 과정을 시뮬레이션하는 프로그램이다.
빙산의 개수를 세는 함수인 CntIce()에서 DFS(Depth First Search) 알고리즘을 사용하여 빙산이 분리된 영역을 찾는다.
main() 함수에서는 빙산의 개수를 체크하고, 빙산이 1개인 경우에는 녹이는 작업을 수행한다.
녹이는 작업은 빙산 주변의 바다의 개수를 세어 빙산을 녹이는 것을 반복하며 수행한다.
만약 빙산이 2개 이상인 경우에는 결과를 저장하고 프로그램을 종료한다.
최종적으로 결과를 출력한다.
