connecting the dots
[BOJ/C++] 2667 : 단지번호붙이기 본문
문제
풀이
1. 완전탐색을 통해 arr[i][j]=1인 가구를 찾는다.
2. 방문한 가구의 값은 key 값으로 바꾸고, 단지 내 다른 가구들을 찾는다.(dfs)
3. for문을 통해 같은 key값을 갖는 가구들 수를 세어 배열에 넣는다.(arrSize 배열)
*
- isInside 함수를 사용해 boundary를 벗어나지 않는지를 체크한다.
- 처음 단지 별 key값을 1,2,3으로 하려고 했으나, key를 1로하면 기존 arr[i][j]=1인 가구와 구분되지 않는다.
- 이웃(동, 서, 남, 북)집에 방문하기 위해 dir[4][2] 배열을 만들어 준다.
- dfs, solution 등 함수를 분리해 작성한다.
- sort 함수를 사용해 배열을 오름차순으로 정렬할 때는 sort(배열이름, 배열이름+개수(숫자))
코드
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 <iostream>
#include <algorithm>
#include<cstdio>
using namespace std;
int n;
int arr[26][26];
int arrSize[323];
int cnt;
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
bool isInside(int a, int b){
return (a>=1 && a<=n) && (b>=1 && b<=n);
}
void dfs(int a, int b, int key){
arr[a][b]=key;
for(int i=0;i<4;i++){
int dx = a + dir[i][0];
int dy = b + dir[i][1];
if(arr[dx][dy]==1 && isInside(dx, dy)){
dfs(dx, dy, key);
}
}
}
void solution(int n){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(arr[i][j]==1){
cnt++;
dfs(i, j, cnt+1);
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(arr[i][j]>1){
arrSize[arr[i][j]-2]++;
}
}
}
}
int main() {
scanf("%d", &n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%1d", &arr[i][j]);
}
}
solution(n);
sort(arrSize, arrSize+cnt);
printf("%d\n", cnt);
for(int i=0;i<cnt;i++){
printf("%d\n", arrSize[i]);
}
return 0;
}
|
cs |
'algorithm > BOJ' 카테고리의 다른 글
[BOJ/Java] 1158 : 요세푸스 문제 (0) | 2021.02.09 |
---|---|
[BOJ/Java] 14503 : 로봇 청소기 (0) | 2021.02.08 |
[BOJ/C++] 2606 : 바이러스 (0) | 2020.12.20 |
[BOJ/C++] 2225번 : 합분해 (0) | 2020.11.09 |
[BOJ/C++] 2579번 : 계단 오르기 (0) | 2020.11.09 |