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

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

 

 

해설 

DFS/BFS로 모든 맵을 탐색하면서 단지를 탐색하면서 Connected Component가 몇개인지 찾아내는 되는 문제이다.

위 예시에서는 3개로 나오기때문에 DFS를 돌려서 DFS가 몇번의 탐색을 했는지 반환하게 하고 이 값을 벡터에 담아둔다.

벡터의 사이즈를 출력하고 벡터를 오름차순 정렬하여 정답을 출력하면된다.

코드를 보며 이해를 하도록 하자.

 

후기

DFS알고리즘을 사용하는데 DFS함수가 몇번의 탐색을 했는지를 반환하는것과 이 정보를 담고 있는 벡터를 활용해야했던 문제인듯하다.

처음에 벡터 대신에 map을 생각했는데 이진 탐색트리 이므로 발견 순서에 따라 출력이 달라질 수 있으니 벡터의 사이즈를 출력하고 오름 차순 정렬하여 출력해야된다는 것을 다시 생각해보게 되었다.

 

코드

#include <iostream>
#include <string>
#include <queue>
#include <map>
#include <algorithm>
#include <stack>
#include <sstream>
#include <set>
#include <unordered_set>
#include <cmath>
using namespace std;
using ll = long long;

const int MAX = 30;
string board[MAX];
bool vis[MAX][MAX];
vector<int> ret;
int n;
int dr[4] = { 0, 1, 0, -1 }, dc[4] = { -1, 0, 1, 0 };

int dfs(int r, int c)
{
	int cnt = 1;
	for (int d = 0; d < 4; ++d)
	{
		int nr = r + dr[d];
		int nc = c + dc[d];
		if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
		if (vis[nr][nc] || board[nr][nc] == '0') continue;
		vis[nr][nc] = true;
		cnt += dfs(nr, nc);
	}
	return cnt;
}

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

	cin >> n;
	for (int i = 0; i < n; ++i) cin >> board[i];
	
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < n; ++j)
		{
			if (vis[i][j] || board[i][j] == '0') continue;
			vis[i][j] = true;
			int cnt = dfs(i, j);
			ret.push_back(cnt);
		}
	}

	cout << ret.size() << endl;
	sort(ret.begin(), ret.end());
	for (int i : ret) cout << i << endl;

	return 0;
}