💡 너비 우선 탐색/깊이 우선 탐색/그래프 이론/그래프 탐색
Memory 10748KB Time 36ms Code Length 961B
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
#include<stdio.h>
#include<algorithm>
using namespace std;
#include<stdio.h>
#include<string>
#include<algorithm>
int map[500][500];
int visited[500][500];
int dy[] = {-1,1,0,0};
int dx[] = {0,0,-1,1};
int n, m;
int dfs(int y, int x, int cnt) {
visited[y][x] = 1;
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 (visited[ny][nx]) continue;
if (map[ny][nx] == 0)continue;
cnt = dfs(ny,nx, cnt +1);
}
return cnt;
}
int result1 = 0;
int result2 = 0;
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]);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (visited[i][j] == 0 && map[i][j] == 1) {
int tmp = dfs(i, j, 1);
if (tmp > result2) {
result2 = tmp;
}
result1++;
}
}
}
printf("%d\n", result1);
printf("%d\n", result2);
}
이 코드는 DFS(깊이 우선 탐색) 알고리즘을 사용하여 2차원 배열 내의 섬의 개수와 각 섬의 크기를 구하는 프로그램이다.
먼저, 사용자로부터 2차원 배열의 크기와 배열의 값을 입력받는다.
방문 여부를 나타내는 visited 배열과 지도를 나타내는 map 배열을 초기화한다.
DFS 함수를 정의하여 해당 위치를 방문하고, 상하좌우로 이동하면서 섬의 크기를 카운트한다.
main 함수에서 모든 위치를 탐색하면서 방문하지 않은 섬이 있는 경우 DFS 함수를 호출하여 섬의 개수를 증가시키고, 가장 큰 섬의 크기를 갱신한다.
마지막으로, 섬의 개수와 가장 큰 섬의 크기를 출력한다.
