티스토리 뷰

#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번: 단지번호붙이기

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여

www.acmicpc.net

 

최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함