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

[백준 2667] 단지번호붙이기(BFS-너비우선탐색)

사용자 BlockDMask 2017. 10. 15. 15:43
반응형
  • 안녕하세요 BlockDMask 입니다.
    171011 일자 문제 입니다.

  • 포스팅을 늦게 했네요;;

  • 이번시간엔 단지번호 붙이기를 BFS 방식으로 풀어보았습니다.

  • 단지 번호 붙이기 DFS 방식으로 푼 포스트는 [여기] 있습니다.

0. 제목

  • 백준 2667 단지 번호 붙이기

  • BOJ 2667 단지 번호 붙이기

1. 문제 설명


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


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


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


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


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


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



2. 풀이 과정


이번에는 자료구조 queue를 이용하여 너비 우선 탐색


 BFS(Breadth First Search)를 이용하여 풀었습니다.


2차원 배열을 표현하기위해 queue에 pair 객체를 집어 넣는 방식을 취했습니다. 


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


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


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


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


단지의 개수로 map[i][j]의 인자를 바꾸어 주고 enqueue(push)를 합니다. (mark)


한 단지안에 여러 집이 있으므로


map[i][j] == 1인 부분을 enqueue(push)하고 상,하,좌,우를 체크 합니다.


한점 i, j에서 더이상 넣을 곳이 없으면 앞에서 부터 pop을 하여 새롭게 얻은 i, j에서 상,하,좌,우를 체크하는 방식입니다.


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



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


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


단지의 최대 개수는 


3*3 = 5

4*4 = 8

5*5 = 13

.

.

입니다.




또한,

a) bfs(너비 우선 탐색)을 반복문을 기반으로 풀어보고

b) bfs(너비 우선 탐색)을 재귀함수 기반으로 풀어보았습니다.


3. 코드


a) 반복문 기반 bfs(너비 우선 탐색)

b) 재귀함수 기반 bfs(너비 우선 탐색)

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
//https://www.acmicpc.net/problem/2667
//BOJ_2667_단지번호 붙이기
 
#include<iostream>
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
 
int n;
int map[25][25];    //정사각형 모양의 지도
int size[323];       // (n*n/2 + 1) 각 단지 집의 수
int cnt;    //단지의 개수 및 번호
int d[4][2= {{10}, {-10}, {01}, {0-1}};
 
bool isInside(int a, int b){
    return (a>=0 && a<n) && (b>=0 && b<n);
}
 
void bfs(int a, int b, int mark){    //[a,b] 좌표, cnt 단지의 번호
 
    queue<pair<intint> > q;
    q.push(pair<intint>(a, b));   //좌표를 넣고
    map[a][b] = mark;    //단지 번호 마킹
 
    while(!q.empty()){  //queue가 비지 않은 동안
        pair<intint> p;
        int y = p.first = q.front().first;
        int x = p.second = q.front().second;
        q.pop();
 
        for(int i=0; i<4; i++){ //up, down, left, right 검사
            if(isInside(y + d[i][0], x + d[i][1]) && map[y + d[i][0]][x + d[i][1]] == 1){   //1이고 내부에있으면
                
                // a) 반복문 기반 bfs(너비 우선 탐색) - (2028KB)
                /*
                map[y + d[i][0]][x + d[i][1]] = mark;    //cnt로  바꿔주고
                q.push(pair<int, int>(y + d[i][0], x + d[i][1]));   //push!
                */
                
                
                //b) 재귀함수 기반 bfs(너비 우선 탐색) - (2160KB)
                bfs(y + d[i][0], x + d[i][1], mark);
            }
 
        }
    }
 
}
 
void Solution(int n){
    for(int i=0; i<n; i++){
        for(int j=0; j<n ;j++){
            if(map[i][j] == 1){ //1을 발견하면
                bfs(i, j, cnt+2);   //bfs 호출
                cnt++;  //단지의 갯수
            }
        }
    }
 
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            if(map[i][j] ==0continue;
 
            size[map[i][j]-2]++;
        }
    }
 
}
 
void Print(){
    printf("%d\n", cnt);
    for(int i=0; i<cnt; i++){
        printf("%d\n"size[i]);
    }
}
 
int main(void){
    //입력
 
    scanf("%d"&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);
 
    //출력
    Print();
 
    return 0;
 
}
cs


4. 인증


a) 반복문 기반 bfs(너비 우선 탐색)


b) 재귀함수 기반 bfs(너비 우선 탐색)


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

감사합니다. 하트 꾹 부탁드립니다

반응형