https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수
www.acmicpc.net
연결 요소를 찾는 문제이다. bfs나 dfs를 사용해서 풀 수 있다.
나는 bfs를 사용해서 풀었다.
아파트가 있고 아직 방문하지 않은(단지 번호가 붙어있지 않은) 모든 칸에 대해서 bfs를 실행해준다.
단지 번호(cnt)는 bfs가 새로 실행될때마다 증가한다.
단지 번호는 num이라는 int형 이차원 배열을 만들어서 붙여주고 이 배열을 사용하여 방문 체크도 해준다.
탐색을 모두 마쳤으면, 각 단지별 아파트 개수를 세준다.
새로운 ans 배열을 만들어서 num배열의 값을 index로 값을 증가시킨다.
즉, ans배열의 1번째에는 단지 번호가 1인 아파트의 개수가 저장되고 ans[2]에는 2번 단지의 개수가 저장된다.
개수를 모두 구해줬으면 문제에서 오름 차순으로 출력하라고 했으므로 정렬해주고 출력한다.
|
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int n;
int cnt;
int map[25][25];
int num[25][25];
int ans[25*25];
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void bfs(int x, int y) {
queue<pair<int,int> > q;
//시작칸 큐에 넣어주고 단지 번호 붙여준다.
q.push(make_pair(x,y));
num[x][y] = cnt;
while(!q.empty()) {
x = q.front().first;
y = q.front().second;
q.pop();
//인전한 칸으로 이동
for(int i=0; i<4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
//범위 벗어나면 넘어간다.
if(nx < 0 || ny < 0 || nx >= n || ny >= n) continue;
//아파트가 있고 아직 방문하지 않은 경우
if(map[nx][ny] == 1 && num[nx][ny] == 0) {
//큐에 넣어주고
q.push(make_pair(nx,ny));
//단지 번호를 붙여준다.
num[nx][ny] = cnt;
}
}
}
}
int main() {
scanf("%d", &n);
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
scanf("%1d", &map[i][j]);
}
}
cnt = 0;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
//집이 있는 곳이고 아직 방문하지 않은 경우 bfs를 실행
if(map[i][j] == 1 && num[i][j] == 0) {
//다음 연결 요소 이므로 단지 번호를 늘려준다.
++cnt;
bfs(i,j);
}
}
}
//총 단지수를 출력
printf("%d\n", cnt);
//각 단지 번호를 인덱스로 ans배열의 값을 증가시킨다.
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(num[i][j] != 0) {
ans[num[i][j]] += 1;
}
}
}
//문제 조건에서 정렬하라고 했으므로 정렬
sort(ans+1, ans+cnt+1);
for(int i=1; i<=cnt; i++) {
printf("%d\n",ans[i]);
}
return 0;
}
Colored by Color Scripter
|
'BOJ' 카테고리의 다른 글
| [BOJ] 2178. 미로 탐색 (0) | 2019.06.25 |
|---|---|
| [BOJ] 4963. 섬의 개수 (0) | 2019.06.25 |
| [BOJ] 14888. 연산자 끼워넣기 (0) | 2019.06.20 |
| [BOJ] 6603. 로또 (0) | 2019.06.20 |
| [BOJ] 10971. 외판원 순회2 (DFS 풀이) (0) | 2019.06.20 |