[알고리즘] 백준알고리즘 2667 단지번호 붙이기 BFS

안녕하세요 감자 코딩에 감자개발자입니다.

이번에 살펴볼 문제는 대표적인 플러드필 알고리즘중 하나인 단지번호붙이기를 BFS로 풀어보도록하겠습니다.

이전에 강의에서 DFS로 풀어보았었는데요, 이번에는 BFS로 다시 풀어보려고 포스팅을 하겠습니다.

 

---

단지번호붙이기 성공

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초

128 MB

34947

13452

8944

38.168%

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입력 1 복사

7 0110100 0110101 1110101 0000111 0100000 0111110 0111000

예제 출력 1 복사

3 7 8 9

 

---

위의 문제를 요약 하겠습니다.

 

 

TESTCASE

1. 정사각형의 모양의 지도가 있음(1 = 집이 있음, 0 = 집이 없음) N(5 <= N <= 25) 이므로 결국 0~30번째 까지의 맵을 생성시켜줘야함.

2. 지도의 연결된 단지를 정의, 단지에 번호를 각각 붙이려고 함.

3. 상하좌우에 대한 BFS수행으로 모든 정점을 방문하여 조건을 체크함.

4. 단, 대각선은 연결된것이 아니다.(대각선의 경우를 제외시키고, 상하좌우에 대해 생각하면 된다는 말)

5. 지도를 입력하여 단지수 출력

6. 오름차순 정렬로 문제 해결 

 

문제 해결 방법

 

일단 0으로 표시된곳은 집이 없는곳을 나타내며, 1로 표시된곳은 집이 있는곳을 나타냅니다.

하지만, 저희가 알아보아야 할 조건중에 하나인 연결된 집들의 단지를 찾아내는것인데요.

그러면 지도에 1로표시된것들이 이어진 하나의 단지들로 이루어지면 하나의 단지가 되겠죠?

쉽게 얘기하면 아파트단지에 이어져있는 모습을 생각하시면 되겠습니다.

 

그러면 이제 BFS로 모든 맵들을 상하좌우로 탐색하면서 진행해가면서 1로 이어진점들을 에게 각각의 단지 번호를 부여시키면 됩니다.

첫번째로 만난 1로 이어진 단지를 예를 들어 1번 단지라고 하겠습니다. 1번단지에 이어진 모든 집들을 순회하고 난후 다시 BFS로 방향을 탐색을 시작하면서 만난 집은 이제 두번째 단지가 되겠죠? 왜냐하면, 저희는 check점을 만들어서 그 부분에 대해 방문여부를 체크 True/False를 하게 되기 때문이죠.

 

네, 그렇게 집에 각각의 고유 번호를 붙여준 후 그 해당 고유번호의 값의 집의 개수를 출력해주면 해당 단지의 총 개수가 나오게 되겠지요?

이것을 코드로 표현해보겠습니다.

 

코드를 보여드리기 이전에, 

 

제가 사용한 변수에 대해 말씀드리겠습니다.

Map 변수는 전역으로 선언하여 전체 지도를 나타내었습니다. 5 <= N <= 25 의 범위이므로 30까지 측정하였습니다.

Check 변수는 전역 선언 및 맵의 방문 여부를 역할을 하였습니다. 해당단지의 값이 들어가게됩니다.

Dir 변수는 상하좌우의 값을 방문해야하므로 이동에 대한 처리를 하였습니다.

Result 변수는 해당 단지의 개수를 저장시키기 위한 변수입니다. 

예를 들어, Check에 있는 배열에 값을 확인하여 그 값이 만약 1이라고 할 경우 그 1번째 단지에 대한 카운팅값을 Result배열에 저장하게 됩니다. 이게 무슨말이냐 말 그대로 1번째 단지에 있는 자식들을 모두 확인하고, 또 2번째 있는 단지에 있는 자식들을 모두 확인하면서 진행하게 됩니다. 

 

 

 

---

소스코드 

//
//  단지번호붙이기.cpp
//  beakjoon_algorithm
//
//  Created by kgh on 29/06/2019.
//  Copyright © 2019 kgh. All rights reserved.
//

#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;

int Map[30][30];
int Check[30][30];
int dir[4][2] = {{-1,0},{1,0},{0,1},{0,-1}};
int Result[625];
int n;
void bfs(int cur_x,int cur_y, int cnt){
    // 들어온 값 넣기
    queue<pair<int,int>> q;
    q.push(make_pair(cur_x,cur_y));
    Check[cur_x][cur_y] = cnt;
    
    while(!q.empty()){
        cur_x = q.front().first;
        cur_y = q.front().second;
        q.pop();
        for(int k=0; k<4; k++){
            int dx = cur_x+dir[k][0];
            int dy = cur_y+dir[k][1];
            if(dx >= 0 && dx < n && dy >= 0 && dy < n){
                if(Map[dx][dy] == 1 && Check[dx][dy] == 0){
                    q.push(make_pair(dx,dy));
                    Check[dx][dy] = cnt;
                }
            }
        }
    }
}
int main(void){
    
    cin >> n;
    
    // 입력된 값들 맵에 저장
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            scanf("%1d",&Map[i][j]);
//            cin >> Map[i][j];
        }
    }
    // bfs
    int cnt=0;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            // 갈수있는 경로고 체크된곳이 아닐경우 bfs수행
            if(Map[i][j] == 1 && Check[i][j] == 0){
                // 단지의 개수를 증가해서 들어가게 되면 1번째 단지부터 시작한다.
                bfs(i,j,++cnt);
            }
        }
    }
    // 총 단지의 개수
    cout << cnt << '\n';
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            // 해당하는 단지의 수를 체크한다
            // 예를 들면, Result[0] = 1번째 단지, Result[1] = 2번째 단지
            Result[Check[i][j]] += 1;
        }
    }
    // 오름 차순 정렬
    sort(Result+1, Result+cnt+1); // TestCase 1: 결과에 저장된 1~3단지의 개수 정렬
    
    for(int i=1; i<=cnt; i++){
        cout << Result[i] << '\n';
    }
    return 0;
}

 

단지번호붙이기 문제 풀이를 마치겠습니다.

 

잘못된 부분이 있거나 다양한 의견주시면 감사히 받아들이겠습니다.

 

이상 감자코딩에 감자개발자입니다.