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

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

DFS와 BFS 두 방법으로 구현 가능하다.

필자는 DFS로 구현하였다.

---

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

using namespace std;

vector<string> map;
vector<vector<bool>> visited;

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

void dfs(int x, int y)
{
	for (int i = 0; i < 4; i++)
	{
		int nextX = x + dx[i];
		int nextY = y + dy[i];

		if ((nextX >= 0 && nextX < N) && (nextY >= 0 && nextY < N))
		{
			if (!visited[nextX].at(nextY) && map[nextX].at(nextY) == '1')
			{
				visited[nextX].at(nextY) = true;
				cnt++;
				dfs(nextX, nextY);
			}
		}
	}
}

int main()
{
	vector<int> answer;

	cin >> N;

	map = vector<string>(N);
	visited = vector<vector<bool>>(N, vector<bool>(N, false));

	for (int i = 0; i < N; i++)
	{
		string temp;
		cin >> temp;

		map[i] = temp;
	}

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			if (!visited[i].at(j) && map[i].at(j) == '1')
			{
				visited[i].at(j) = true;
				cnt = 1;
				dfs(i, j);

				answer.push_back(cnt);
			}
		}
	}
	
	sort(answer.begin(), answer.end());

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

	for (int i = 0; i < answer.size(); i++)
		cout << answer[i] << '\n';

	return 0;
}

count를 dfs에 넣어서 하고 싶었지만 도저히 방법이 떠오르지 않아서 전역변수로 설정하였다.

dx와 dy를 이용하여 왼쪽 아래쪽 오른쪽 위쪽 순서로 확인하였다.

 

각 위치에 방문하였나 확인한 후 진행하다가 도달할 수 있는 지역이 없으면 count 값을 정답 벡터에 넣어주고 다음 단지를 확인할 때 1로 초기화해주었다. (시작하는 자리도 하나의 집이기 때문에 1로 초기화한다.)