# 2667. 단지번호붙이기

관련 알고리즘 : BFS

문제 링크 : https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

---

문제 풀이

 

지도를 모두 돌며 연결되어 있는 단지의 개수와 단지 당 집 개수를 찾아야 하므로 bfs(너비우선탐색)을 이용한다.

 

플로우는 다음과 같다.

1. string을 통해 입력 처리
2. map 완전탐색을 통해 아직 방문하지 않고 & 좌표값이 1인 경우(집이 있는 경우) 부터 bfs 시작
3. 상하좌우 탐색 이후,
   1. 지도 밖의 범위일 경우 반복문 탈출
   2. 이미 방문한 곳일 경우 반복문 탈출
   3. 1,2 모두 해당되지 않을 경우 queue에 넣고 방문처리
4. bfs 한번 돌 때마다 count++ 통해 단지 개수 출력
5. bfs 내에서 연결된 집 개수 count++ 통해 단지 내 집 개수 출력

 

주의할 점은, 입력이 n개씩 한번에 n번 들어오므로

입력을 받을 때 string을 사용하여 한번에 받고 이후 처리를 통해 이차원배열에 넣어주는 작업을 해줘야 한다.

---

C++ 코드

#include <iostream>
#include <queue>
#include <algorithm>

using namespace std;
#define MAX 26

int n; // 지도의 크기
int cnt = 0; // 단지 수 세기용
int map[MAX][MAX];
int visit[MAX][MAX]={0,};
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0}; // 상하좌우 탐색
vector<int> res; // 단지 하나당 집 개수 저장용 vector
queue<pair<int, int>> que; // (x,y) 값 저장용 큐

void bfs() {

    int cnt = 0; // 한 단지 당 집 개수 세기

    while(!que.empty()) {
        int x = que.front().first;
        int y = que.front().second;
        cnt += 1; // 단지 내 집 개수 추가

        que.pop();

        for(int i=0; i<4; i++) {
            int next_x = x+dx[i];
            int next_y = y+dy[i];

            if(next_x<0 || next_x>=n || next_y<0 || next_y>=n) // 지도 밖을 벗어나는 경우
                continue;

            if(visit[next_x][next_y] == 1) // 이미 방문했을 시
                continue;
            else if(map[next_x][next_y] == 1) { // 방문하지 않았고, 집이 존재할 때
                que.push({next_x, next_y}); // que에 넣기
                visit[next_x][next_y] = 1; // 방문처리
            } 
        }
    }
    res.push_back(cnt);
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i = 0; i<n; i++)
    {
        string tmp;
        cin >> tmp;
        for(int j = 0 ; j< n; j++)
        {
            map[i][j] = tmp[j]-'0';
        }
    }   

    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            // 아직 방문하지 않고, 집이 있는 곳부터 시작
            if(map[i][j]==1 && visit[i][j]==0) {
                cnt ++; // 처음 시작하는 곳이므로 cnt+1 해주고 시작
                que.push({i,j}); // 큐에 시작 위치 넣기
                visit[i][j] = 1; // 방문처리
                bfs(); // 시작위치를 기준으로 bfs
            }
        }
    }

    sort(res.begin(), res.end());
    cout << cnt << '\n';

    for(int i=0; i<res.size(); i++) {
        cout << res[i] << '\n';
    }

}