백준 2667번: 단지번호붙이기

[문제 링크]

2667번: 단지번호붙이기

---

현재 좌표에서 동서남북 방향을 깊이 우선 탐색 함으로써 한 단지에 속하는 좌표를 방문하고 집의 개수를 저장하였다.

그리고 한번 깊이 우선 탐색을 했는데 방문하지 않은 좌표가 존재한다면 또다른 단지가 존재하는 것이므로 그 좌표를 시작으로 다시 깊이 우선 탐색 하는 것을 반복하도록 구현하였다.

---

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

int N;
vector<string> board(25);
bool visited[25][25];

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

struct Pos 
{
	int y;
	int x;
};

int dfs(Pos here)
{
	int ret = 1;

	for (int i = 0; i < 4; i++)
	{
		int ny = here.y + dy[i];
		int nx = here.x + dx[i];

		if (ny >= 0 && ny < N && nx >= 0 && nx < N)
			if (!visited[ny][nx] && board[ny][nx] == '1')
			{
				visited[ny][nx] = true;
				ret += dfs({ ny, nx });
			}
	}

	return ret;
}

int main(void) 
{
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> board[i];

	vector<int> result;
	for(int i=0; i<N; i++)
		for(int j=0; j<N; j++)
			if (!visited[i][j] && board[i][j] == '1')
			{
				visited[i][j] = true;
				Pos start = { i,j };
				result.push_back(dfs(start));
			}

	sort(result.begin(), result.end());

	cout << result.size() << endl;
	
	for (int i = 0; i < result.size(); i++)
		cout << result[i] << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 163 day