[백준/BOJ] 백준 2667번 : 단지번호붙이기

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

2667번: 단지번호붙이기

단지를 발견할 때마다 dfs를 시작해 해당 단지의 집 개수를 센다.

 

코드

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

vector<string> board;
int n;
int num;
vector<int> home_num;
int dx_dy[4][2] = { {0,-1},{0,1},{-1,0},{1,0} };

void solve(pair<int,int> here)
{
	//해당 단지의 집 개수를 증가한다
	num++;

	//탐색하는 집(개수를 센 집)을 없앤다
	board[here.first][here.second] = '0';

	//인접한 부분을 dfs한다
	//단 인접한 부분이 범위를 벗어나지 않아야 하고 '1' (집)이어야 한다
	for (int i = 0; i < 4; i++)
	{
		pair<int, int> there = make_pair(here.first + dx_dy[i][0], here.second + dx_dy[i][1]);
		if (there.first >= 0 && there.first < n && there.second >= 0 && there.second < n && board[there.first][there.second] == '1')
		{
			solve(there);
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	string temp;
	
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		board.push_back(temp);
	}

	for(int i=0; i<n; i++)
		for (int j = 0; j < n; j++)
		{
			//단지를 발견한것이므로 dfs를 시작해 해당 단지의 집 개수를 센다
			if (board[i][j] != '0')
			{
				num = 0;
				solve(make_pair(i, j));

				//dfs하고난뒤 num이 해당 단지의 집 개수이다
				home_num.push_back(num);
			}
		}

	//오름차순으로 정렬한다
	sort(home_num.begin(), home_num.end());

	cout << home_num.size() << "\n";

	for (int i = 0; i < home_num.size(); i++)
	{
		cout << home_num[i] << "\n";
	}

	return 0;
}