문제링크: https://www.acmicpc.net/problem/2667

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

풀이

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

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

int arr[25][25];
bool visited[25][25];

int lineCount;

void dfs(int x, int y, const int& size) {
	visited[x][y] = true;
	lineCount++;

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

		if (nx < 0 || nx >= size || ny < 0 || ny >= size) {
			continue;
		}

		if (!visited[nx][ny] && arr[nx][ny] == 1) {
			dfs(nx, ny, size);
		}
	}
}

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

	int N; std::cin >> N;
	std::vector<int> ans;

	for (int i = 0; i < N; i++) {
		std::string s; std::cin >> s;

		for (int j = 0; j < N; j++) {
			arr[i][j] = (int)s[j] - 48;
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (!visited[i][j] && arr[i][j] == 1) {
				lineCount = 0;

				dfs(i, j, N);

				ans.push_back(lineCount);
			}
		}
	}

	std::sort(ans.begin(), ans.end());

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

	return 0;
}

dx와 dy방향 벡터를 선언하고 옆으로 이동하며 방문 했는지 안 했는지를 dfs로 판별한다.
집이 이어져있으니 집의 개수 count를 늘려간다.
그렇게 dfs로 탐색을 했으면, 정답 벡터에 추가한 후
단지 개수(벡터 원소 개수)를 출력하고 집 개수(벡터의 각 원소)를 출력하면 되는 간단한 문제였다.

노트

문제를 너무 dfs로만 푸는 감이 있지만 일단 오랜만에 하는 것이기 때문에 먼저 익숙해져야겠다.
bfs가 떠오르면 bfs로 풀겠지만 그렇지 않다면 dfs를 중점으로 문제를 풀어갈 생각이다.