[백준] 단지 번호 붙이기 (BFS)

바로 이어서 BFS로 풀어보자.

 

이전 글과 똑같은 문제

 

BFS로 쉽게 풀 수 있었다. 코드는 아래와 같다.

 

#include <stdio.h>
#define MAX 25
#define INFI 999999

int Map[MAX][MAX];
int SizeStorage[MAX * MAX];

typedef struct Queue {
	int x;
	int y;
} Queue;
Queue Q[INFI];
int front = -1, rear = -1;

int BFS (int x, int y, int limit) {
	// 왼, 오, 위, 아 방향 계산
	int sumSize = 1;
	int directX[] = {-1, 1, 0, 0};
	int directY[] = {0, 0, -1, 1};
	
	// 시작 지점 추가
	rear++;
	Q[rear].x = x;
	Q[rear].y = y;
	
	// 방문 표시
	Map[y][x] = 0;
	
	// 너비 탐색 시작
	while (front < rear) {
		// 큐에서 값빼기
		front++;
		
		// 염색체도 아니고 ...
		int x = Q[front].x;
		int y = Q[front].y;
		
		// 왼, 오, 위, 아 방향 체크
		for (int i = 0; i < 4; i++) {
			// 새로운 좌표 방향 계산
			int nextX = x + directX[i];
			int nextY = y + directY[i];
			
			// 아래 조건에 해당하는 경우 이동 불가
			if (nextX < 0 || nextX == limit || nextY < 0 || nextY == limit) {
				continue;
			}
			
			// Map에서 이동 가능한 좌표인 경우
			if (Map[nextY][nextX] == 1) {
				// 다음 이동 리스트에 등록
				rear++;
				Q[rear].x = nextX;
				Q[rear].y = nextY;
				
				// 방문 표시
				Map[nextY][nextX] = 0;
				
				// 사이즈 증가
				sumSize++;
			}
		}
	}
	
	return sumSize;
}

void selectionSort (int sortCount) {
	for (int i = 0; i < sortCount - 1; i++) {
		// 정렬 대상 위치의 인덱스 값을 최소값으로 저장
		int min = i;
		
		// 정렬 대상의 위치를 제외한 나머지에서 최소값 찾기
		for (int j = i + 1; j < sortCount; j++) {
			// 최소값이 있는 인덱스 구하기
			if (SizeStorage[min] > SizeStorage[j]) {
				min = j;
			}
		}
		
		// 정렬 대상이 최소값이라면 다음 아이템 진행
		if (i == min) {
			continue;
		}
		
		// 스왑
		int temp = SizeStorage[i];
		SizeStorage[i] = SizeStorage[min];
		SizeStorage[min] = temp;
	}
}

int main(void) {
	int N = 0;
	int S = 0;
	int C = 0;
	
	scanf("%d", &N);
	
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			scanf("%1d", &Map[y][x]);
		}
	}
	
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			if (Map[y][x]) {
				// 단지 갯수 + 1
				C++;
				
				// BFS 시작
				S = BFS(x, y, N);
				
				// 정보 저장
				SizeStorage[C - 1] = S;
			}
		}
	}
	
	// 오름차순 정렬
	selectionSort(C);
	
	// 답출력
	printf("%d\n", C);
	
	for (int i = 0; i < C; i++) {
		printf("%d\n", SizeStorage[i]);
	}
	
	return 0;
}

 

 

BFS는 DFS와 달리 자료구조 큐가 필요하므로 메모리를 많이 먹는 것이 단점이다. 하지만 코드가 DFS의 재귀와는 달리 디버깅 시 가독성이 좋고 무한 루프에 빠질 위험이 없어 최소 비용이나 미로 찾기에 사용된다. 참고로 DFS로 미로 찾기를 하는 경우, 도착 지점으로 갈 수 없는 경우에는 무한 루프에 빠진다.

 

선택 정렬

 

선택 정렬이란 반복문 수행 시 가장 작은 값 혹은 큰 값을 선택하여 왼쪽부터 차례대로 정렬하는 방법으로 시간 복잡도는 버블 정렬과 동일하지만 상대적으로 Swap이 덜 일어나므로 버블 정렬보다 아주 약간 빠른 성능을 가지고 있다.

 

선택 정렬

 

메인 루프에서 min 값을 왼쪽 인덱스로 초기화 한 후 배열[min] > 배열 [j] 을 체크한다.

 

void selectionSort (int sortCount) {
	for (int i = 0; i < sortCount - 1; i++) {
		// 정렬 대상 위치의 인덱스 값을 최소값으로 저장
		int min = i;
		
		// 정렬 대상의 위치를 제외한 나머지에서 최소값 찾기
		for (int j = i + 1; j < sortCount; j++) {
			// 최소값이 있는 인덱스 구하기
			if (SizeStorage[min] > SizeStorage[j]) {
				min = j;
			}
		}
		
		// 정렬 대상이 최소값이라면 다음 아이템 진행
		if (i == min) {
			continue;
		}
		
		// 스왑
		int temp = SizeStorage[i];
		SizeStorage[i] = SizeStorage[min];
		SizeStorage[min] = temp;
	}
}