[BOJ/C++] 2667 : 단지번호붙이기

문제

www.acmicpc.net/problem/2667

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(배열이름, 배열이름+개수(숫자))

 

 

코드

#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;
}