[BOJ] 2667 단지번호붙이기 C++

개요

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

2667번: 단지번호붙이기

실버급 DFS, BFS 문제다.

풀이

재귀를 활용한 DFS로 풀었다.

반복문으로 배열(N*N)을 하나씩 체크하고,

1을 발견하면 DFS로 크기를 체크하고 단지수를 증가시키도록 했다.

단지 수는 재귀가 처음 호출 될 때에만 증가할 수 있도록 isFirst(bool) 변수를 사용했다.

마지막 출력 값(각 단지 크기)을 오름차순 정렬하여 출력해야 함에 주의해야 한다.

정렬 안 해서 몇 번 틀렸다(!),,

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
constexpr int LIMIT = 30;

int house[LIMIT][LIMIT]{};
bool visited[LIMIT][LIMIT]{};
int ans;
bool isFirst;
vector<int> cnt;

void dfs(int y, int x)
{
	if (visited[y][x] || !house[y][x]) return;
	if (isFirst)
	{
		ans++;
		cnt.push_back(0);
	}
	isFirst = false;
	visited[y][x] = true;
	cnt.back()++;

	dfs(y, x - 1);
	dfs(y, x + 1);
	dfs(y - 1, x);
	dfs(y + 1, x);
}

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

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			scanf("%1d", &house[i][j]);
		}
	}

	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			isFirst = true;
			dfs(i, j);
		}
	}

	sort(cnt.begin(), cnt.end());
	vector<int>::iterator iter;
	cout << ans << "\n";
	for (iter = cnt.begin(); iter != cnt.end(); iter++)
		cout << *iter << "\n";
}