백준 2667 단지번호붙이기 [DFS]

문제 링크 : https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

문제 풀이

기존 DFS에 정렬을 섞은 문제입니다.

따로 방문 배열 필요 없이, DFS를 탐색하면서 탐색한 지점을 0으로 만들고, 단지의 수를 구합니다.

DFS를 끝나게 되면, 한 단지의 수를 vector에 저장해놓고, 다음 단지를 찾아가면 됩니다.

 

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>

#define MAX_SIZE 25 + 1
using namespace std;

int dx[] = { 0,0,-1,1 };
int dy[] = { 1,-1,0,0 };

int a[MAX_SIZE][MAX_SIZE];
int N, house_cnt, cnt;

vector<int> ans;

void dfs(int x, int y)
{
	cnt++;
	a[x][y] = 0;
	for (int i = 0; i < 4; i++)
	{
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && ny >= 0 && nx < N && ny < N)
		{
			if (a[nx][ny]) dfs(nx, ny);
		}
	}
}

int main()
{
	//freopen("input.txt", "r", stdin);
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			scanf("%1d", &a[i][j]);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (a[i][j])
			{
				cnt = 0;

				dfs(i, j);          
				house_cnt++;        // 단지 추가
				ans.push_back(cnt); // 각 단지내의 집의 수 저장
			}
		}
	}

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

	return 0;
}