[백준] 2667번 단지번호붙이기

문제: 2667번: 단지번호붙이기

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

basic-algo-lecture/workbook/0x09.md at master · encrypted-def/basic-algo-lecture

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <unordered_set>
#include <unordered_map>
#include <queue>

using namespace std;

int n;
int used[25][25]; // 방문 여부
int board[25][25]; // 현재 지도 상태
priority_queue<int, vector<int>, greater<int>> houseCnts;

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

int BFS(int x, int y) {
    // 야 진입하자마자 이미 방문한 곳 또는 갈 수 없는 곳이면 걍 빠져나가
    if (board[x][y] == 0 || used[x][y] == 1) {
        return 0;
    }

    // 이제 탐색 시작행
    queue<pair<int, int>> nexts;
    nexts.push({ x,y });
    used[x][y] = 1; // 방문 표시
    int houseCnt = 0;
    while (!nexts.empty()) {
        pair<int, int> cur = nexts.front();
        nexts.pop();
        houseCnt++;
        
        // 다음으로 갈 곳 nexts 에 저장해!
        for (int i = 0; i < 4; i++) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];

            if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
            if (used[nx][ny] == 1 || board[nx][ny] == 0) continue;

            nexts.push({ nx, ny });
            used[nx][ny] = 1; // 방문 표시!
        }
    }
    // 최소힙에 넣어줭
    houseCnts.push(houseCnt);
    return 1; // 여기까지 온거면 단지 하나 더 찾은거임
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        string input;
        cin >> input;

        for (int j = 0; j < n; j++) {
            board[i][j] = input[j] - '0';
        }
    }

    // 이중포문 돌면서 단지의 개수 찾아
    // 그리고 단지 속 집의 개수도 찾아서 최소힙에 넣어
    int totalCnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            totalCnt += BFS(i, j);
        }
    }
    cout << totalCnt << "\n";
    while (!houseCnts.empty()) {
        cout << houseCnts.top() << "\n";
        houseCnts.pop();
    }

    return 0;
}

 

~_~ 오랜만에 BFS 문제 풀었는데 재밌었당.

 

각 단지의 집의 개수를 오름차순으로 정렬해서 출력해야 했는데 그냥 쉽게 하려고 최소힙 사용했다. BFS 돌면서 찾은 각 단지의 집 개수들을 최소힙에 저장해놓으면 그냥 마지막에 while 문 돌면서 출력하는 방식으로 쉽게 해결할 수 있다!