백준이당
[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