[백준 C++] 2667 단지번호붙이기 - 깊이우선탐색

2667번: 단지번호붙이기

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

int Complex = 0;
vector<int> Map;
vector<vector<int>> Neighbors;
vector<int> Households;

int NumberingComplex(int HouseIndex)
{
	int Count = 1;
	Map[HouseIndex] = Complex;

	for (int& Neighbor : Neighbors[HouseIndex])
	{
		if (Map[Neighbor] == 0)
		{
			Count += NumberingComplex(Neighbor);
		}
	}

	return Count;
}

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

	Map.reserve(n * n);
	for (int i = 0; i < n * n; ++i)
	{
		char Character = cin.get();
		if (Character == '\n') Character = cin.get();
		Map.emplace_back(Character - '0' - 1);
	}

	Neighbors.reserve(n);
	for (int i = 0; i < n * n; ++i)
	{
		Neighbors.emplace_back(vector<int>());
	}

	int i = 0;
	for (const int& House : Map)
	{
		if (House == 0)
		{
			// top
			if (i / n > 0 && i - n >= 0
				&& Map[i - n] == 0)
			{
				Neighbors[i].emplace_back(i - n);
			}

			// bottom
			if (i / n < n - 1 && i + n < n * n
				&& Map[i + n] == 0)
			{
				Neighbors[i].emplace_back(i + n);
			}

			// left
			if (i % n > 0 && i - 1 >= 0
				&& Map[i - 1] == 0)
			{
				Neighbors[i].emplace_back(i - 1);
			}

			// right
			if (i % n < n - 1 && i + 1 < n * n
				&& Map[i + 1] == 0)
			{
				Neighbors[i].emplace_back(i + 1);
			}
		}

		++i;
	}

	i = 0;
	for (const int& House : Map)
	{
		if (House == 0)
		{
			++Complex;
			Households.emplace_back(NumberingComplex(i));
		}

		++i;
	}

	sort(Households.begin(), Households.end());

	cout << Complex << '\n';
	for (const int& Household : Households)
	{
		cout << Household << '\n';
	}
}

---

 

다음과 같은 순서로 진행되도록 코드를 작성했습니다.

 

1. 지도 정보 저장

2. 이웃 정보 저장

3. 단지 번호 붙이기 - 재귀함수 (DFS) & 단지별 세대수 저장

4. 단지별 세대수 정렬

5. 단지별 세대수 출력

 

이웃 정보 저장 단계에서 조건을 잘 설정해주는 것이 중요했습니다.