💡 너비 우선 탐색/깊이 우선 탐색/그래프 이론/그래프 탐색
Memory 2028KB Time 0ms Code Length 1273B
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
#include <iostream>
#include <utility>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> loc;
bool cmp(const int &first, const int &second) {
return first < second;
}
int N;
int num; // 단지 수
char MAP[25][26];
int visited[25][25];
vector <int> result;
void init() {
cin >> N;
num = 0;
for (int i = 0; i < N; i++) {
cin >> MAP[i];
}
}
void bfs(loc param) {
const int dy[] = { -1,0,1,0 };
const int dx[] = { 0,-1, 0 ,1 };
num++;
queue<loc> q;
q.push(param);
visited[param.first][param.second] = 1; // 방문 처리
int cnt = 1; // 단지 내 집 수
while (!q.empty()) {
loc now = q.front(); q.pop();
for (int i = 0; i < 4; i++) {
int ny = now.first + dy[i];
int nx = now.second + dx[i];
if (ny < 0 || nx < 0 || ny >= N || nx >= N) continue;
if (visited[ny][nx] == 1) continue;
if (MAP[ny][nx] == '0') continue;
visited[ny][nx] = 1;
q.push({ ny,nx });
cnt++;
}
}
result.push_back(cnt);
}
int main() {
init();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (MAP[i][j] == '0') continue;
if (visited[i][j] == 1) continue;
bfs({ i,j });
}
}
cout << num << "\n";
sort(result.begin(), result.end(), cmp);
for (int r : result) {
cout << r << "\n";
}
}
이 코드는 N*N 크기의 지도에서 1로 표시된 집들이 서로 연결된 단지를 찾아내는 프로그램이다.
init 함수에서 N을 입력받고 MAP 배열에 지도 정보를 저장한다.
bfs 함수는 주어진 시작 위치부터 상하좌우로 집이 있는 곳을 탐색하며 해당 단지의 집 수를 센다. 이때, 방문한 곳은 visited 배열을 통해 체크한다.
main 함수에서 모든 지도를 순회하면서 아직 방문하지 않은 집이 있는 경우 bfs 함수를 호출하여 해당 단지의 집 수를 센다.
단지 수(num)와 각 단지의 집 수를 result 배열에 저장한 뒤, 결과를 출력한다. 결과는 단지 수와 각 단지의 집 수를 오름차순으로 출력한다.
Memory 1232KB Time 0ms Code Length 929B
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
#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int n;
char map[25][26];
int visited[25][25];
priority_queue<int, vector<int>, greater<int>> pq;
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };
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 >= n || ny < 0 || nx < 0) continue;
if (visited[ny][nx] == 1) continue;
if (map[ny][nx] == '0') continue;
cnt = dfs(ny, nx, cnt + 1);
}
return cnt;
}
int main()
{
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf(" %s", map[i]);
}
int cnt = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == '0') continue;
if (visited[i][j] == 1) continue;
pq.push(dfs(i, j, 1));
cnt++;
}
}
printf("%d\n", cnt);
for (int i = 0; i < cnt; i++) {
int tmp = pq.top(); pq.pop();
printf("%d\n", tmp);
}
}
이 코드는 주어진 2차원 배열(map)에서 ‘1’로 표시된 영역의 개수와 각 영역의 크기를 구하는 프로그램이다.
- dfs 함수는 재귀적으로 상하좌우로 이동하면서 방문하지 않은 ‘1’인 지점을 찾아가며 해당 영역의 크기를 구한다.
- main 함수에서는 2차원 배열을 입력받고, 모든 지점을 탐색하면서 ‘1’인 지점을 발견하면 dfs 함수를 호출하여 해당 영역의 크기를 구하고 우선순위 큐에 저장한다.
- 마지막에는 총 영역의 개수와 각 영역의 크기를 출력한다.
