c언어 2667번 단지번호붙이기 (백준)

#include <stdio.h>

int sum = 0; //dfs에서 몇개인지를 담는 변수
int n; //n*n
int map[26][26] = {0}; //처음 0 또는 1을 입력받음
int check[26][26] = {0}; //이미확인 했는지 안 했는지

int dfs(int i, int j) //depth first search
{
	if(map[i][j] == 1 && check[i][j] == 0) //1이고, 확인 안 한 것일 때
	{
		sum++;
		check[i][j]++;
		if(j > 0) dfs(i, j-1); //왼쪽으로
		if(j < n-1) dfs(i, j+1); //오른쪽으로
		if(i > 0) dfs(i-1, j); //위로
		if(i < n-1) dfs(i+1, j); //아래로
	}
}

int main(void)
{
	int ans[314] = {0}; //dfs에서 구한 sum값을 저장
	int cnt = 0; //sum값이 1이상으로 마무리 될 때마다 증가
	scanf("%d", &n);
	
	for(int i = 0; i<n; i++) { //input
		char s[26] = {0};
		scanf("%s", s);
		for(int j = 0; j<n; j++) {
			if(s[j] != 0) map[i][j] = s[j]-48;
		}	
	}
	
	for(int i = 0; i<n; i++) { //dfs
		for(int j = 0; j<n; j++) {
			if(map[i][j] == 1 && check[i][j] == 0)dfs(i, j);
			if(sum > 0) {
				ans[cnt++] = sum;
			}
			sum = 0;
		}
	}
	//shell sort : 오름차순
	int i, j;
	int gap = n/2;
	int key = 0;
	while(1)
	{
		if(gap % 2 == 0) gap++;
		for(i = gap; i<cnt; i++)
		{
			key = ans[i];
			for(j = i - gap; j>=0; j-=gap)
			{
				if(key < ans[j]) ans[j+gap] = ans[j];
				else break;
			}
			ans[j+gap] = key;
		}
		if(gap == 1) break;
		gap /= 2;
	}
	
	
	printf("%d\n", cnt); //단지 개수
	for(int i = 0; i<cnt; i++) printf("%d\n", ans[i]); //오름차순으로 출력
}

 

풀이 : DFS (Depth First Search) _ 깊이우선탐색

을 이용한다.

 

i = 0, j = 0부터 진행하며, 입력 받은 값이 1이며, dfs에서 확인 된 적이 없을 때 (check[i][j] = 0) dfs을 한다.

dfs에서 벗어날  때 sum값이 1 이상이면, 따로 저장한다.

 

따로 저장한 것(ans[])을 오름차순 정렬 한 뒤, 출력하면 된다. (저장한 것들의 개수와 함께)

 

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

2667번: 단지번호붙이기