💡 너비 우선 탐색/브루트포스 알고리즘/깊이 우선 탐색/그래프 이론/그래프 탐색
Memory 1424KB Time 20ms Code Length 1387B
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
#include<stdio.h>
#include<string.h>
int n;
int map[100][100];
int state[100][100];
int max = 1;
int max_high;
void make_state_map(int k) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (state[i][j]) continue;
if (map[i][j] <= k) {
state[i][j] = 1;
}
}
}
}
int dy[] = { -1,0,1,0 };
int dx[] = { 0,-1,0,1 };
int tmp_visited[100][100];
void dfs(int y, int x) {
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (ny >= n || nx >= n || ny < 0 || nx < 0) continue;
if (tmp_visited[ny][nx]) continue;
if (state[ny][nx]) continue;
tmp_visited[ny][nx] = 1;
dfs(ny, nx);
}
}
int max_find() {
memset(tmp_visited, 0, sizeof(tmp_visited));
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (state[i][j] == 1) continue; // 잠겼다면 패스
if (tmp_visited[i][j] == 1) continue; // 이미 방문했다면 패스
tmp_visited[i][j] = 1;
dfs(i,j);
cnt++;
}
}
return cnt;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
scanf(" %d", &map[i][j]);
max_high = max_high > map[i][j] ? max_high : map[i][j];
}
}
for (int i = 0; i < max_high; i++) {
make_state_map(i); // state 맵 갱신
// max 값 확인해보기
int land_num = max_find();
max = max > land_num ? max : land_num;
}
printf("%d\n", max);
}
make_state_map함수는map을 기준으로state배열을 만들어주는 함수이다.map[i][j]가k보다 작거나 같으면 해당 위치의state[i][j]를 1로 설정한다.dfs함수는 깊이 우선 탐색을 수행하는 함수이다. 현재 위치에서 상하좌우를 탐색하면서 방문하지 않은 곳이 있으면 재귀적으로 호출하여 탐색을 진행한다.max_find함수는state배열을 기준으로 땅의 개수를 세는 함수이다. 이미 방문한 곳이거나 잠겨있는 곳은 세지 않고, 새로운 땅을 발견할 때마다dfs함수를 호출하여 연결된 땅을 모두 탐색한다.main함수에서는 입력을 받고,max_high값을 찾은 뒤make_state_map과max_find함수를 호출하여 최대 땅의 개수를 찾아 출력한다.
