본문 바로가기
<알고리즘 문제풀이&연습>/[C++] 백준

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

by 사용자 BlockDMask 2017. 10. 12.
반응형
  • 안녕하세요.  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)


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
//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= { {-10}, {10}, {0-1}, {01}};    //상하좌우 확인을 위한 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(sizesize + cnt); //정렬(오름차순으로)
 
    //출력
    cout << cnt << endl;
    for(int i=0; i<cnt; i++){
        cout << size[i] << endl;
    }
 
    return 0;
}
cs


4. 인증


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

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

반응형

댓글7

  • !! 2018.10.18 15:52

    상하좌우를 위해 dir[4][2]로 선언을 하셨는데 왜 4, 2인지 모르겠어요!!! ㅠㅠ 이유를 좀 알려주세용 ..ㅠㅠ
    답글

    • 아하 이것은
      3x3 이차원 배열을 생각해보면,
      [0][0] [0][1] [0][2]
      [1][0] [1][1] [1][2]
      [2][0] [2][1] [2][2]
      가운데 [1][1] 이 제가 지금 있는 위치라고 생각을 해볼게요.

      여기서
      위쪽으로 가기위해서는 [0][1]로 가야겠죠? 그러면 [1][1] 에서 [-1][0] 을 더해주면 갈 수 있겠죠?
      아래로 가기위해서는 [1][1] -> [2][1]이 되어야하니까 [1][1]인 위치에서 [1][0]을 더해주면 되겠죠?
      이런식으로해서
      왼쪽은 [0][-1]
      오른쪽은 [0][1] 을 더해주는 겁니다.
      이걸 따로따로 선언을 해도 되는데,
      상 : [-1][0]
      하 : [1][0]
      좌 : [0][-1]
      우 : [0][1]
      이렇게 모아 놓고 보니까! 따로따로 관리하는거보다. "오! 그러면 2차원배열 4x2로 관리하면 더 편리하겠는데? "
      라고 생각해서 dir[4][2]로 선언해서 문제를 풀었습니다.

  • 2019.03.23 14:08

    비밀댓글입니다
    답글

  • Terry Shin 2019.03.27 20:41

    안녕하세요. 알고리즘 문제 풀다 질문이 있어 남깁니다. BlockDMask님이 푼 방식과 거의 유사하기 풀었는데 백준 제출 시 자꾸 틀렸다고 나오는데 이유를 모르겠네요.
    혹시 실례가 안된다면 한번 봐주실 수 있을까요????

    아 그리고 저는 비전공자인데 개발자 취준 준비중입니다. 그래서 BlockDMask님 블로그 굉장히 자주 참고하게 되는데요. 혹시 공부하시는 커리큘럼 같은게 있으신가요?

    #include <cstdio>
    #include <vector>
    #include <algorithm>
    using namespace std;

    int n;
    int arr[25][25] = {0,};
    int visited[25][25] = {0,}; // 문제에 그림 예시처럼 보여주기 위해서 int 선언하고 몇번째 단지 인지 저장
    int dir[4][2] = {{0,-1}, {0,1}, {1,0}, {-1,0}};
    int cnt = 0; // 단지의 개수
    int cnt2 = 0; // 단지내 아파트의 개수
    int size[(25*25)/2 + 1] = {0,};

    void DFS(int a, int b, int cnt){

    visited[a][b] = cnt;
    cnt2++;
    size[cnt] = cnt2;

    for(int i = 0; i < 4; i++){
    int next_x = a + dir[i][0]; // 0
    int next_y = b + dir[i][1]; // 1

    if(visited[next_x][next_y] == 0 && arr[next_x][next_y] == 1 && next_x >= 0 && next_x < n && next_y >= 0 && next_y < n){
    DFS(next_x, next_y, cnt);
    }
    }
    }

    int main(){

    scanf("%d",&n);
    for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
    scanf("%d", &arr[i][j]);
    }
    }

    for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
    if(arr[i][j] == 1 && visited[i][j] == 0){
    cnt++; // 단지의 수는 계속 하나씩 늘려감.
    cnt2 = 0; // 아파트의 수는 초기화
    DFS(i,j,cnt);
    }
    }
    }

    if(cnt == 0){ // 단지의 수가 0 일 떄
    printf("%d\n",cnt);
    printf("%d\n",0);
    }else{ // 단지가 있으면

    printf("%d\n",cnt); // 단지의 개수 출력
    stable_sort(size+1, size+cnt+1);

    for(int i = 1; i <= cnt; i++){
    printf("%d\n",size[i]);
    }
    }

    return 0;
    }
    답글

    • 안녕하세요.
      BlockDMask 입니다.
      우선, 제 블로그를 많이 방문해주셔서 감사합니다.

      코드를 살펴보니
      알고리즘 문제가 아니라 바로 "입력"받는 데에 문제가 있었습니다.

      코드를 직접 돌려보시면, 맨 처음 n을 받고 그 n을 arr[][] 2차원 배열에 넣는 scanf가 있습니다.

      지금은 "%d"로 받아주셨는데요.
      이거는 %d는 엔터를 입력할때까지의 숫자를 받게 됩니다.
      01010101 하고 엔터가 들어오면
      arr[0][0] 에 01010101이 들어가게 됩니다.

      이걸 한자리 숫자만 받으려면 "%1d" 로 변경하시면 됩니다.
      그러면 0101010 엔터를 누르면 scanf가 한번에 하나의 숫자씩 받으면서 반복문을 이쁘게 돌 수 있습니다.

      Terry Shin님께서 구현하신 코드로는 scanf에서 무제한으로 기다리기 때문에 아마 시간초과가 나왔을것 입니다.

      결론 : 입력 데이터가 제대로 들어오지 않았습니다.
      scanf("%d", arr[i][j]) -> scanf("%1d", arr[i][j]) 로 변경.

      문제가 해결되었으면 좋겠습니다.
      또 방문해주세요. 감사합니다.

      ps. 커리큘럼은 Terry Shin님께서 어디를 목표로 공부하고 계신지를 알수없어서 답변드리기가 모호 하네요. 저도 배우는 입장이라 ㅠㅠ 곤란하네요

  • CHOCHOCHO 2019.07.26 19:27

    안녕하세요.
    DFS 이론 공부하고 문제에 적용하는 법이 감이 안잡혔는데 코드 참고하면서 너무 도움이 되었네요.
    감사합니다.
    DFS, BFS를 이제 감을 잡아가고있는데

    문제를 풀다보면 탐색을 해야할때
    꼭 DFS를 사용해야하거나 꼭 BFS를 사용할 때가 생기나요?
    상대적으로 다른 자료구조 사용안하고.. 재귀로만 할 수 있는 DFS가 편해서 BFS에는 손이 잘 안가네요..
    혹시 그런 경우가 있다면 간단한 예시 몇개 가능할까요..?

    코드 참고하러 자주 오겠습니다. 좋은자료 감사합니다~

    답글

  • 2020.01.21 21:51

    비밀댓글입니다
    답글