백준이당

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

이히당 2025. 4. 5. 16:28

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

완전 기본적인 bfs문제다.

감다뒨줄 알았는데 다행이당..ㅎ

1. 문제 분석

간단히 문제 설명이다.

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

 

1은 집이고 0은 집이 아니다.
1끼리 묶여있는 곳이 '단지'다.
단지의 개수를 출력하고, 단지에 있는 집이 몇 개인지 오름차순으로 출력하면 된다.

 


 

나는 여기서 오름차순 출력을 위해 우선순위 큐를 사용했다.

    priority_queue<int, vector<int>, greater<int>> ansPQ;

 

주의할 점이라면,


priority_queue는 반복자(iterator)를 지원하지 않는다는 점이다.

priority_queue는 내부적으로 heap 자료구조를 사용하기 때문에
begin(), end() 같은 반복자 기반 순회를 할 수 없다.

 

해당 부분을 유의해서 답을 출력하면 된다.

2. 풀이

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

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

bool isVisited[26][26];
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n;
    cin >> n;
    vector<string> board(n);
    for (int i = 0; i < n; i++)
    {
        /* code */
        cin >> board[i];
    }

    queue<pair<int, int>> q;
    priority_queue<int, vector<int>, greater<int>> ansPQ;
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            // 집이 없거나 이미 방문한 곳이라면 패스
            if (board[i][j] == '0' || isVisited[i][j])
            {
                continue;
            }

            int cnt = 0;
            q.push({i, j});
            isVisited[i][j] = true;

            while (!q.empty())
            {
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                cnt++;

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

                    // 범위를 넘어가거나, 집이 없거나(0), 이미 방문 했었다면 패스
                    if (nx < 0 || nx >= n || ny < 0 || ny >= n || board[nx][ny] == '0' || isVisited[nx][ny])
                    {
                        continue;
                    }

                    q.push({nx, ny});
                    isVisited[nx][ny] = true;
                }
            }

            ansPQ.push(cnt);
        }
    }

    cout << ansPQ.size() << "\n";

    while (!ansPQ.empty())
    {
        cout << ansPQ.top() << "\n";
        ansPQ.pop();
    }
}
728x90