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

문제

[C++] 백준 2667: 단지번호붙이기 SILVER 1
https://www.acmicpc.net/problem/2667

 

---

 

접근 방법

이 문제는 지도에서 1로 표시된 집들이 상하좌우로 연결되어 있을 때,

각 단지(연결 요소) 의 개수와 단지별 집의 수를 구하는 문제이다.

 

지도는 n × n 크기의 격자이므로, 모든 칸을 순회하면서 아직 방문하지 않은 집(1)을 만나면 BFS를 시작한다.
BFS로 연결된 모든 집을 탐색하면 하나의 단지가 완성되며, 탐색 과정에서 방문한 집의 개수를 세어 단지 크기로 저장한다.

 

이 과정을 전체 지도에 대해 반복한 뒤, 단지의 개수와 각 단지의 크기를 오름차순으로 정렬해 출력하면 된다.

 

구현 시 주의할 점

• BFS를 시작할 때 초기 집도 단지 크기에 포함되므로 카운트를 1부터 시작해야 한다.

 

---

 

코드

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
using namespace std;

vector<vector<int>> home;
vector<vector<bool>> visited;
int n;
int dy[4] = { -1,1,0,0 };  // 상하좌우
int dx[4] = { 0,0,-1,1 };

int bfs(int y, int x)
{
	queue<pair<int, int>> Q;
	Q.push(make_pair(y, x));
	visited[y][x] = true;

	int cnt = 1;
	while (!Q.empty())
	{
		int now[2] = { Q.front().first, Q.front().second };
		Q.pop();

		for (int i = 0; i < 4; i++)
		{
			int yy = now[0] + dy[i];
			int xx = now[1] + dx[i];

			if (yy < 0 || n <= yy || xx < 0 || n <= xx
				|| home[yy][xx] == 0 || visited[yy][xx] == true)
				continue;

			Q.push(make_pair(yy, xx));
			visited[yy][xx] = true;
			cnt++;
		}
	}
	return cnt;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	home.resize(n, vector<int>(n, 0));
	visited.resize(n, vector<bool>(n, false));
	for (int y = 0; y < n; y++)
	{
		string str = "";
		cin >> str;
		for (int x = 0; x < n; x++)
		{
			home[y][x] = str[x] - '0';
		}
	}

	vector<int> cnt;  
	for (int y = 0; y < n; y++)
	{
		for (int x = 0; x < n; x++)
		{
			if (home[y][x] == 1 && visited[y][x] == false)
				cnt.push_back(bfs(y, x));
		}
	}

	cout << cnt.size() << '\n';
	
	sort(cnt.begin(), cnt.end());
	for (int i = 0; i < cnt.size(); i++)
		cout << cnt[i] << '\n';

	return 0;
}