코딩공작소
[백준]단지번호붙이기 본문
https://www.acmicpc.net/problem/2667
2667번: 단지번호붙이기
<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수
www.acmicpc.net
은근히 배울게 많은 문제... 뭔가 이번에 이것때문에 틀린거같은데 . .?
각 단지,섬(인접한 것들)마다 번호붙이고 그것의 개수도 세는 ... dfs로가면서 몇번가는지 개수를 세는...
저번 시험에서는 파라미터로 넘겼다가 개수를 이상하게 세서 상당히 고민했었는데 ...
|
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
|
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int map[25][25];
bool isV[25][25];
int dr[] = { 0,0,-1,1 }, dc[] = { 1,-1,0,0 };
int cnt = 0;
int cnt2 = 0;
vector<int> v;
void dfs(int r, int c) {
isV[r][c] = true;
cnt2++; //글로벌로 세주어야함 ..
for (int i = 0; i < 4; i++) {
int nr = r + dr[i], nc = c + dc[i];
if (nr < 0 || nc < 0 || nr >= N || nc >= N)continue;
if (!isV[nr][nc] && map[nr][nc]) dfs(nr, nc);
}
}
void solve() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (!isV[i][j] && map[i][j]) {
cnt2 = 0; // 몇개의 원소로 이루어져 있나...
dfs(i, j);
cnt++; // 섬의 개수.
v.push_back(cnt2);
}
}
}
sort(v.begin(), v.end());
printf("%d\n", cnt);
for (int i = 0; i < v.size(); i++) printf("%d\n", v[i]);
}
int main()
{
cin >> N;
for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) scanf_s("%1d", &map[i][j]);
solve();
return 0;
}
|
cs |