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

1. 문제

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

2667번: 단지번호붙이기

 

2. 풀이

: 전형적인 flood fill 문제입니다. 주어진 2차원 배열을 탐색하며 1(아직 방문하지 않은 집)을 만나면 cnt를 증가시킨 후 상하좌우에 인접한 모든 집들을 dfs로 방문하면서 cnt+1값으로 채워줍니다. 이후 각 영역의 크기를 계산하고 오름차순으로 정렬하여 출력합니다. 이 문제에서 주의할 점은 입력을 받을 때, 띄어쓰기 없이 입력이 들어오므로 "%1d"를 이용해서 입력을 처리해줍니다.

 

 

3. 코드

#include <iostream>
#include <algorithm>

using namespace std;
int A[30][30], n, Size[400], cnt = 0;
int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, -1, 1};

void input() {
	scanf("%d", &n);
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) scanf("%1d", &A[i][j]);
	}
	
}

bool safe(int a, int b) {
	return (0<=a && a<n) && (0<=b && b<n);
}

void dfs(int a, int b, int c) {
	A[a][b] = c;
	for(int i=0; i<4; i++) {
		if(safe(a+dx[i], b+dy[i]) && A[a+dx[i]][b+dy[i]] == 1) 
		dfs(a+dx[i], b+dy[i], c);
	}
}

void solve() {
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			if(A[i][j] == 1){
				cnt++;
				dfs(i, j, cnt+1);
			}
		}
	}
	for(int i=0; i<n; i++) {
		for(int j=0; j<n; j++) {
			if(A[i][j]) Size[A[i][j] - 2]++;
		}
	}
	sort(Size, Size+cnt);
}

void output() {
	printf("%d\n", cnt);
	for(int i=0; i<cnt; i++) printf("%d\n", Size[i]);
}

int main(void) {
	
	iostream::sync_with_stdio(false);
	cin.tie(NULL);
	input();
	solve();
	output();
	return 0;
}