백준 - 2667 단지 번호 붙이기

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

본문제는 전형적인 섬찾기 알고리즘 문제이며 bfs 를 반복하면서 답을 쉽게 찾을 수 있다.

문제의 전략은 아래와 같다.

 

1. 맵의 시작부터 각각 순회 하면서 방문하지 않은 곳을 선택한다.

2. 선택된 위치에서 bfs 로 방문하면서 방문한 총 가구수를 계산한다.

3. 모든 가구를 순회하면서 1~2단계를 반복한다.

4. 계산된 각각의 숫자들의 개수와 숫자들을 오름차순 정렬하여 출력한다.

 

구현된 코드는 아래와 같다.

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;

int update(vector<vector<int>> &m, const int rStart, const int cStart, int groupId);

int main()
{
	int sz;
	cin >> sz;

	vector<vector<int>> m(sz, vector<int>(sz, 0));

	for (int r = 0; r < sz; r++)
	{
		string s;
		cin >> s;
		for (int c = 0; c < sz; c++)
		{
			m[r][c] = s[c] - '0';
		}
	}

	int groupId = 2;
	vector<int> resultList;
	for (int r = 0; r < sz; r++)
	{
		for (int c = 0; c < sz; c++)
		{
			if (m[r][c] == 1)
			{
				int res = update(m, r, c, groupId++);
				resultList.push_back(res);
			}
		}
	}
	cout << groupId - 2 << endl;
	sort(resultList.begin(), resultList.end());
	for_each(resultList.begin(), resultList.end(), [](int &c){
		cout << c << endl;
	});
}

int update(vector<vector<int>> &m, const int rStart, const int cStart, int groupId)
{
	queue<pair<int, int>> q;
	q.push(make_pair(rStart, cStart));

	const int adjMap[4][2] = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
	const int &mSize = m.size();

	int result = 1;
	m[rStart][cStart] = groupId;
	
	while (!q.empty())
	{
		auto d = q.front();
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int rNext = d.first + adjMap[i][0];
			int cNext = d.second + adjMap[i][1];

			if (rNext < 0 || rNext >= mSize) continue;
			if (cNext < 0 || cNext >= mSize) continue;

			if (m[rNext][cNext] != 1) continue;

			m[rNext][cNext] = groupId;
			result++;
			q.push(make_pair(rNext, cNext));
		}
	}
	return result;
}