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

이번에는 DFS / BFS 심화 문제를 풀어보도록 하자. 이 문제는 DFS와 BFS 두 가지 방법 모두 가능하며 이번 글에서는 DFS로 풀어보았다. 다음 글에서 동일한 문제를 BFS로 풀어보도록 하겠다.

 

백준 2667

이번 문제는 2차원 배열에서 이동 가능한 경로를 찾기 위해 상, 하, 좌, 우 모든 방향을 살펴 보는것이 핵심이다. 코드를 살펴보자.

 

#include <stdio.h>
#define MAX 25
int Map[MAX][MAX];
int SizeStorage[MAX * MAX];

int DFS (int x, int y, int limit, int size) {
	// 왼, 오, 위, 아 방향 계산
	int sumSize = size;
	int directX[] = {-1, 1, 0, 0};
	int directY[] = {0, 0, -1, 1};
	
	// 방문 표시
	Map[y][x] = 0;
	
	// 왼, 오, 위, 아 방향 체크
	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) {
			// DFS 실행
			sumSize = DFS(nextX, nextY, limit, sumSize + 1);
		}
	}
	
	return sumSize;
}

void bubbleSort (int sortCount) {
	for (int i = 0; i < sortCount; i++) {
		for (int j = i + 1; j < sortCount; j++) {
			int temp = SizeStorage[i];
			
			if (SizeStorage[j] < SizeStorage[i]) {
				SizeStorage[i] = SizeStorage[j];
				SizeStorage[j] = 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++;
				
				// DFS 시작
				S = DFS(x, y, N, 1);
				
				// 정보 저장
				SizeStorage[C - 1] = S;
			}
		}
	}
	
	// 오름차순 정렬
	bubbleSort(C);
	
	// 답출력
	printf("%d\n", C);
	
	for (int i = 0; i < C; i++) {
		printf("%d\n", SizeStorage[i]);
	}
	
	return 0;
}

 

2차원 배열에서 상, 하, 좌, 우 방향으로 이동하기

 

이 문제의 핵심은 2차원 배열에서 이동 가능한 곳을 찾기 위해 상, 하, 좌, 우를 모두 체크하는 것이다. 나는 왼쪽 -> 오른쪽 -> 위쪽 -> 아랫쪽 순으로 체크하였다. 4가지 방향에 대해서만 체크하면 되기 때문에 반복문을 4번 돌리고 아래와 같이 X, Y 좌표를 자동으로 계산하도록 코드를 작성하였다.

 

왼쪽 체크 시 = 현재 X - 1, 현재 Y + 0

오른쪽 체크 시 = 현재 X + 1, 현재 Y + 0

위쪽 체크 시 = 현재 X + 0, 현재 Y - 1

아랫쪽 체크 시 = 현재 X + 0, 현재 Y + 1

 

코드로 나타내면 아래와 같다.

 

int nextX[] = {-1, 1, 0, 0};
int nextY[] = {0, 0, -1, 1};

 

이제 이 코드를 반복문으로 해당 인덱스에 해당하는 값들을 더하면 다음 이동할 좌표를 자동으로 계산 할 수 있다.

 

DFS 리턴 이용하기

 

이전에 이 문제를 DFS로 풀 때 전역 변수를 하나 선언하고, 방문할 때마다 + 1을 하는 방법으로 문제를 풀었는데 이번에는 좀 다른 방법으로 풀어보았다. 재귀문의 리턴을 사용하여 풀었는데 약간의 시행착오가 있어서 남겨본다.

 

재귀문의 리턴을 사용 했을 때 문제가 되는 부분의 코드를 살펴보자.

 

sumSize = DFS(nextX, nextY, limit, sumSize + 1);

 

원래 코드에는 sumSize + 1 이 아닌 DFS 함수의 마지막 파라미터인 size + 1 이였는데, 이 경우 재귀문의 특징 때문에 오답이 출력될 수 있다. 글로 적으면 복잡하니 코드를 돌려봐서 확인해보자.

 

sumSize = DFS(nextX, nextY, limit, size + 1);

 

위와 같이 코드를 변경하고, DFS로 탐색하는 과정을 출력해보자.

 

누적치가 잘못 계산되는 문제

스크린샷의 단지 사이즈는 다음 좌표로 이동 직전의 사이즈를 나타낸 것이다. 출력을 살펴보자. 2차원 배열 (1, 2) 에서 분기문이 있는 것을 볼 수 있다. (1, 2) 에서 왼쪽과 오른쪽으로 이동 가능하기 때문에 위의 스크린 샷과 같이 탐색하는 것이다. 여기서 가장 중요한 단지 사이즈를 살펴보자. 데이터가 누적되지 않고 이전 사이즈를 그대로 출력하고 있다. 왜 이런일이 발생하는 것일까?

 

(1, 2) 에서 왼쪽인 (0, 2)로 이동할 때 상황을 살펴보자. 참고로 (1, 2) 에서 다음 좌표로 이동하기 직전의 size 값은 5다. (1, 2)에서 (0, 2)로 이동하면 size + 1을 하여 6이된다. (0, 2)에서는 이동할 수 없으므로 6을 리턴하고 직전 호출인 (1, 2)로 돌아간다.

 

(1, 2)에서 오른쪽 이동이 가능하므로 (2, 2)로 이동한다. 이 때, 리턴 값이 아닌 size + 1 을 해버리기 때문에 (1, 2) 함수가 호출 될 때 가지고 있던 size 값인 5로 계산한다. 즉, 누적치가 아닌 (1, 2)가 호출 되었을 때의 size 값으로 다시 계산해버리는 것이다.

 

따라서 올바른 값을 출력하기 위해서는 sumSize + 1 로 계산해야한다. 바꿔서 출력해보자.

 

누적치로 계산한 정답

(0, 2)에서 리턴된 6으로 (1, 2) -> (2, 2) 이동 시 값을 + 1 하므로 답이 7이 출력된다. 당연한 내용인데 재귀문에 익숙하지 않으면 이와 같은 실수를 하게된다.

 

버블 정렬

 

이 문제에는 그래프 탐색 뿐만 아니라 정렬도 알고 있어야만 풀 수 있다. DFS 풀이에서는 가장 기초적인 버블 정렬을 사용하였다. BFS 풀이에서는 선택 정렬로 풀어보도록 하겠다.

 

버블 정렬은 아이템 i와 아이템 i + 1의 크기를 비교하여 위치를 서로 바꿔주는 아주 기본적인 정렬이다.

 

버블 정렬

위의 그림과 같이 버블 정렬은 아이템 총 갯수 - 1 만큼 반복하여 바로 옆의 아이템과 비교하여 위치를 바꾼다. 한번 반복문이 호출될 때마다 모든 아이템을 체크하기 때문에 배열의 크기가 커지면 급격한 성능 저하가 오게 된다. 그럼에도 불구하고 구현하기 쉬운 장점이 있어 빠른 속도가 요구되지 않거나 이렇게 알고리즘 문제를 풀 때 자주 사용되기도 한다.

 

버블 정렬 코드는 아래와 같다.

 

void bubbleSort (int sortCount) {
	for (int i = 0; i < sortCount - 1; i++) {
		for (int j = i + 1; j < sortCount; j++) {
			int temp = SizeStorage[i];
			
			if (SizeStorage[j] < SizeStorage[i]) {
				SizeStorage[i] = SizeStorage[j];
				SizeStorage[j] = temp;
			}
		}
	}
}

 

다음 글에서는 같은 문제를 BFS로 풀어보도록 하겠다.