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

1. 문제

https://www.acmicpc.net/problem/2667

2. 입력/출력

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

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

3. 풀이

섬의 개수(4963)와 유사한 문제이다.
차이점은 섬의 개수에서는 땅의 넓이를 세지 않아도 되었지만, 이 문제에서는 땅의 넓이도 세주어야 한다.
DFS를 돌 수 있는 땅일 때 마다 카운트를 올려주면 단지의 아파트 수를 셀 수 있다.

주의점

'오름차순'으로 답을 출력해야 한다.

4. 코드

using namespace std;
int n;
int map[26][26];
int check[26][26];
int apart = 0;
int answer = 1;

int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

void DFS(int x, int y) {
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];

        if (nx<n && ny<n && nx>=0 && ny>=0) {
            if (check[nx][ny] == 0 && map[nx][ny]==1) {
                check[nx][ny] = 1;
                answer++;
                DFS(nx, ny);
            }
        }
    }
}

int main()
{

    cin >> n;

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

    vector<int> arr;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (check[i][j] == 0 && map[i][j] == 1) {
                check[i][j] = 1;
                DFS(i, j);
                apart++;
                arr.push_back(answer);
                answer = 1;
            }
        }
    }
    sort(arr.begin(), arr.end());

    cout << apart << "\n";
    for (int i = 0; i < apart; i++) {
        cout << arr[i]<<"\n";
    }
}