[BOJ]2667번: 단지번호붙이기

2667번: 단지번호붙이기

전체 탐색을 돌아서 해결하는 문제다. 나는 내 코드가 bfs인지 dfs인지는 모르겠다. 아시는 분은 댓글 달아주시면 감사드리겠습니다.

앞으로 문제를 열심히 풀어서 탐색 문제 같은 기본적이고 필수적인 문제들은 마스터를 하도록 노력해야 겠다는 생각을 했다.

	#include <cstdio>
	#include <vector>
	#include <algorithm>
	using namespace std;
	int N, ans[313];
	char map[26][26];
	int dx[4] = { 1, 0, -1, 0 }, dy[4] = { 0, 1, 0, -1 };
	void func(int x, int y, int cnt)
	{
	if (y < 0 || y > N - 1 || x < 0 || x > N - 1) return;
	map[x][y] = '0';
	++ans[cnt];
	for (int i = 0; i < 4; i++) {
	if (map[x + dx[i]][y + dy[i]] == '1')
	func(x + dx[i], y + dy[i], cnt);
	}
	}
	int main()
	{
	scanf("%d", &N);
	int cnt = 0;
	for (int i = 0; i < N; i++) {
	scanf("%s", &map[i]);
	}
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
	if (map[i][j] == '1') {
	cnt++;
	func(i, j, cnt);
	}
	}
	}
	printf("%d\n", cnt);
	sort(ans + 1, ans + cnt + 1);
	for (int i = 1; i <= cnt; i++) {
	printf("%d\n", ans[i]);
	}
	return 0;
	}

view raw 2667.cpp hosted with ❤ by GitHub