백준 2667 단지번호붙이기 (C++)

 

숫자 이차원 배열에서 1로 저장되어있는 덩어리를 찾아내서 처리하는 문제.

이차원 배열을 훑어 나가다가 1로 저장되어있고 방문한 적 없다면

dfs를 활용해서 해당 묶음을 한번에 처리하는 식으로 구현한다.

#include <iostream>
#include <algorithm>
#include <vector>
#include<string>
#include<cstring>
#include<queue>
#include<cmath>
using namespace std;
int arr[26][26];
bool check[26][26];
int n;
int housecount;
int d = 0;
priority_queue<int,vector<int>,greater<int> > numlist;
void dfs(int row, int col);
int main()
{
	string temp;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		for (int j = 0; j < n; j++)
		{
			arr[i][j] = temp[j] - '0';
		}
	}
	memset(check, 0, sizeof(check));
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (arr[i][j] == 1 && check[i][j]==0) {
				housecount = 0;
				dfs(i, j);
				numlist.push(housecount);
				d++;
			}
				
		}
	}
	cout << d << "\n";
	for (int i = 0; i < d; i++)
	{
		cout<<numlist.top()<<"\n";
		numlist.pop();
	}
}
void dfs(int row, int col)
{
	if (check[row][col] == true || arr[row][col] == 0) return;

	check[row][col] = true;
	housecount++;
	if (row > 0)
		dfs(row - 1, col);
	if (row < n-1)
		dfs(row+ 1, col);
	if (col > 0)
		dfs(row, col-1);
	if (col < n-1)
		dfs(row, col + 1);
}