알고리즘 :: 백준 :: DFS :: 2667:: 단지번호붙이기

문제

문제접근

문제 이해

• 이 문제는 전형적인 쉬운 DFS 또는 BFS 문제 유형입니다.
  조금 더 적나라하게 말하자면, DFS 쪽에 조금 더 친숙한 유형입니다.
  (DFS는 재귀(스택)를 이용하다보니 코드 줄 수가 4~6줄이면 됩니다.)
• main()같은 외부 함수에서 for()문을 돌며 2차원 배열의 아직 방문하지 않은 모든 점에 대해 DFS 또는 VFS를 돕니다.
• 더 이상 연결된 점이 없어서 진행이 불가능할 때 하나의 단지를 카운팅합니다.
• 이제 2차원 배열을 탐색하며 방문하지 않은 다른 점들 중 단지인 점을 찾습니다.
• 더 이상 방문하지 않은 점이 없을 때까지 반복합니다.

코드

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

int N, cnt, d[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
bool map[27][27], visited[27][27];

void dfs(int y, int x) {
	cnt++;
	visited[y][x] = true;
	for (int i = 0; i < 4; ++i) {
		int ny = y + d[i][0], nx = x + d[i][1];
		if (!visited[ny][nx] && map[ny][nx]) dfs(ny, nx);
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N;
	string row;
	for (int y = 1; y <= N; ++y) {
		cin >> row;
		for (int x = 1; x <= N; ++x)
			map[y][x] = (row[x - 1] == '1') ? true : false;
	}
	vector<int> ans;
	for (int y = 1; y <= N; ++y)
		for (int x = 1; x <= N; ++x)
			if (map[y][x] && !visited[y][x])
				dfs(y, x), ans.push_back(cnt), cnt = 0;
	sort(begin(ans), end(ans));
	cout << ans.size() << '\n';
	for (int i : ans) cout << i << '\n';
}

결과