[백준 / C언어] 2667번: 단지번호붙이기

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

2667번: 단지번호붙이기

 

난이도: solved.ac 실버 1

 

 

사용 알고리즘

---

DFS (BFS도 가능)

 

 

 

접근 방법

---

DFS와 BFS 알고리즘 기본 문제다

먼저 for문을 이용해 한 칸씩 이동하며 집을 찾아주고, 집을 찾으면 해당 집이 속한 단지를 DFS를 이용해 찾아주었다

이때 집의 개수도 size라는 변수를 통해 세어주었다

그리고 한 단지의 탐색이 끝나면 num이라는 배열에 위에서 구한 size를 저장시켜주었다

이 과정을 반복하고 모든 단지의 탐색이 끝나면 qsort를 이용해 배열 num을 오름차순으로 정렬시켜주었다

 

여기서 num의 크기가 400인데, 이는 원래 최대 단지의 수가 313(13*13 + 12* 12)개지만 313이라는 숫자보다는 400이라는 숫자가 깔끔해보여서 넉넉하게 400으로 잡아준 것이다

 

그리고 DFS를 탐색하는 동안 배열 바깥 index로는 이동하지 못하게 배열의 index를 넘어가는 경우에는 DFS를 실행하지 않도록 해주었다

 

(코드)

#include<stdio.h>
#define MAX 26

int map[MAX][MAX];
int visited[MAX][MAX];
int num[400];
int size;

void DFS(int i, int j, int N);

int compare(int* a, int* b) {
	return *a - *b;
}

int main() {
	int N, i, j, cnt = 0;
	scanf("%d", &N);

	for (i = 0; i < N; i++)
		for (j = 0; j < N; j++)
			scanf("%1d", &map[i][j]);

	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			if (map[i][j] && !visited[i][j]) {
				DFS(i, j, N);
				num[cnt] = size;
				cnt++;
				size = 0;
			}
		}
	}
	qsort(num, cnt, sizeof(int), compare);
	printf("%d\n", cnt);
	for (i = 0; i < cnt; i++)
		printf("%d\n", num[i]);
	return 0;
}

void DFS(int i, int j, int N) {
	visited[i][j] = 1;
	size++;
	if (i - 1 >= 0)
		if(map[i - 1][j] && !visited[i - 1][j])
			DFS(i - 1, j, N);
	
	if (j - 1 >= 0)
		if(map[i][j - 1] && !visited[i][j - 1])
			DFS(i, j - 1, N);
	if (map[i + 1][j] && !visited[i + 1][j])
		DFS(i + 1, j, N);
	if (map[i][j + 1] && !visited[i][j + 1])
		DFS(i, j + 1, N);
}