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

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

2667번: 단지번호붙이기

#include <cstdio>
#include <algorithm>
int N;
char city_map[25 + 2][25 + 2];
int visited[25 + 2][25 + 2];
int danji;
int cnt;
int ans[25 * 25 + 2];

void input(void)
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%s", &city_map[i]);
	}
}


void DFS(int x, int y)
{
	static int dir_x[4] = { 0, 0, 1, -1 };
	static int dir_y[4] = { 1, -1, 0, 0 };
	
	visited[x][y] = 1;

	for (int p = 0; p < 4; p++) {
		int nx = x + dir_x[p];
		int ny = y + dir_y[p];
		if (nx < 0 || nx > N - 1 || ny < 0 || ny > N - 1) continue;
		if (city_map[nx][ny] == '0') continue;
		if (visited[nx][ny] == 1) continue;
		cnt++;
		DFS(nx, ny);
	}
}



void get_danji(void)
{
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (city_map[i][j] == '0') continue;
			if (visited[i][j] == 1) continue;
			cnt = 1;
			DFS(i, j);
			ans[danji] = cnt;
			danji++;
		}
	}
}


void output(void)
{
	printf("%d\n", danji);
	std::sort(ans, ans + danji);
	for (int i = 0; i < danji; i++) {
		printf("%d\n", ans[i]);
	}
}


int main()
{
	input();
	get_danji();
	output();
	return 0;
}

나샊... 이 문제 정리 안하려고 했는데 똑같은 부분 계속 틀려서 기록해본다. 

 

내가 틀린 부분은 다음과 같다.

1) ans 배열의 최대 크기를 25로 잡아주면 안된다. 맵의 크기가 최대 25 * 25가 될 수 있기 때문에 단지 수는 더 많이 나올 수 있다. 

2) 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력해야 한다. 

 

 

다른건.. 일반적인 Flood Fill 문제와 동일하다. 

오늘의 반성.. 문제에서 주는 조건좀 잘 읽자...