[백준 2667] 단지번호붙이기(DFS-깊이우선탐색)

• 안녕하세요.  BlockDMask 입니다.

• 날이 갑자기 추워졌네요;; 다들 ;; 옷 따숩게 입으시길;;

• 오늘자 문제 시작하겠습니다.

• 이번 포스트는 단지번호 붙이기를 DFS 방식으로 풀었습니다.

• 단지번호 붙이기 BFS 방식으로 푼 글은 [여기] 있습니다.

0. 제목

• 백준 2667 단지 번호 붙이기

• BOJ 2667 단지 번호 붙이기

1. 문제 설명

<그림 1>과 같이 정사각형(5<=N<=25) 모양의 지도가 있습니다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타냅니다.

철수는 이 지도를 가지고 연결된 집들의 모임을 단지로 정의하고, 단지에 번호를 붙이려 합니다.

여기서 연결 되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말합니다.

대각선상에 집이 있는 경우는 연결된 것이 아닙니다.

<그림 2>는 <그림 1>을 단지 별로 번호를 붙인 것입니다.

지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

2. 풀이 과정

깊이 우선 탐색

DFS(Depth First Search)를 이용하여 풀었습니다.

2차원 배열로 이루어진 MAP에서

첫번째 줄 (i=0)에서부터 탐색을 시작하여, map[i][j] ==1 인 부분이 나타나면

단지가 시작되는 부분이므로 단지의 개수(cnt)를 하나 증가시킨 후 

그 점부터 이어진 모든 곳에 대해 DFS(깊이 우선 탐색)을 시작합니다.

단지의 개수로 map[i][j]의 인자를 바꾸어 줍니다. (key)

연결되어있는 여러 집이 한 단지 안에 있으므로.

그런식으로 탐색을 하여 단지의 개수와 그 단지안의 집의 개수를 구합니다.

각 단지들을 저장할 배열은 n*n/2 +1 개로 배열의 크기를 잡았습니다.

대각선인 경우에는 단지로 셈하지 않으므로

단지의 최대 개수는 

3*3 = 5

4*4 = 8

5*5 = 13

.

.

n*n /2 +1 이 최대 입니다.

3. 코드

추가적으로 제가 int size라고 전역변수로 지었는데, 대댓글을 달러 이제와서 코드를 확인하니 size라는게 여러 키워드로 쓰이다보니 좋지 않은 변수명이라는걸 이제야 알게 되었습니다. size 말고 arrSize라든지 mapSize라든지 이런 이름으로 변경하는게 더 좋을것 같습니다. (2019.03.28)

//https://www.acmicpc.net/problem/2667
//BOJ_2667_단지 번호 붙이기
 
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
 
 
int map[25][25];    //정사각형 모양의 지도
 
int size[323];  //단지의 집 개수 [ (n*n/2) + 1개 ]
                //대각선은 이어진게아니므로 크기가 n일때 집의 최대 개수
 
int dir[4][2] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}};    //상하좌우 확인을 위한 2차원 배열
 
int cnt;    //단지의 개수
 
int n;  //입력받을 n 
 
//좌표가 배열의 범위를 넘지 않는지
bool isInside(int a, int b){
    return (a>=0 && a<n) && (b>=0 && b<n);
}
 
//재귀를 통한 깊이 우선 탐색(dfs)
void dfs(int a, int b, int key){
    map[a][b] = key;
 
    for(int i=0; i<4; i++){
        int dy = a + dir[i][0];
        int dx = b + dir[i][1];
 
        if(isInside(dy, dx) && map[dy][dx] == 1){
            dfs(dy, dx, key);
        }
    }
}
 
void Solution(int n){
    for(int i=0; i<n; i++){ //맵을 탐색하면서 1인 부분을 찾으면
        for(int j=0; j<n; j++) {
            if (map[i][j] == 1) {   //dfs로 보낸다
                cnt++;
                dfs(i, j, cnt + 1);
            }
        }
    }
 
    for(int i=0; i<n; i++){ //dfs에서 key값을 통해서 각 dfs마다 숫자를 지정해 놓았습니다
        for(int j=0; j<n; j++){
            if(map[i][j] >1){   //같은 숫자의 갯수를 더해서 배열에 집어 넣습니다
                size[map[i][j] - 2]++;
            }
        }
    }
}
 
int main(void){
    //입력
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n;j++) {
            scanf("%1d", &map[i][j]);   //숫자 하나씩 입력 받습니다
        }
    }
 
    Solution(n);
    sort(size, size + cnt); //정렬(오름차순으로)
 
    //출력
    cout << cnt << endl;
    for(int i=0; i<cnt; i++){
        cout << size[i] << endl;
    }
 
    return 0;
}

4. 인증

문제 및 그림 출처 - https://www.acmicpc.net/problem/2667

감사합니다. 셨다면하꾺꾺꾺