[종만북]6.무식하게 풀기-소풍

문제

출처 : https://algospot.com/judge/problem/read/PICNIC

안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.

각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요. 짝이 되는 학생들이 일부만 다르더라도 다른 방법이라고 봅니다. 예를 들어 다음 두 가지 방법은 서로 다른 방법입니다.

(태연,제시카) (써니,티파니) (효연,유리)
(태연,제시카) (써니,유리) (효연,티파니)

입력
입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 학생의 수 n (2 <= n <= 10) 과 친구 쌍의 수 m (0 <= m <= n*(n-1)/2) 이 주어집니다. 그 다음 줄에 m 개의 정수 쌍으로 서로 친구인 두 학생의 번호가 주어집니다. 번호는 모두 0 부터 n-1 사이의 정수이고, 같은 쌍은 입력에 두 번 주어지지 않습니다. 학생들의 수는 짝수입니다.

출력
각 테스트 케이스마다 한 줄에 모든 학생을 친구끼리만 짝지어줄 수 있는 방법의 수를 출력합니다.

풀이

풀이에 앞서 브루트 포스(Brute force), 다른 말로 무식하게 풀어보기 방식은 가능한 모든 경우를 시도해보는 알고리즘 방식으로, 완전 탐색 방식이라고 부른다. 이 방식에 있어서 효과적으로 모든 경우를 시도하는 방법 중 하나가 재귀 함수를 사용하는 것인데, 이 문제의 경우에서도 재귀 함수를 이용한 풀이를 하였다. 재귀 함수의 사용에 있어서 핵심적인 개념은 다음과 같다고 생각한다.

N개의 원소 중 M개의 원소 선택

원소를 선택하는 재귀함수(){
	반복문{
		x개의 원소를 선택한 상태로 설정(전역변수 또는 매개변수 활용)
		재귀함수를 호출하여 나머지 M-x개의 원소를 선택
		다시 x개의 원소를 선택 해제
	}
}

즉, 재귀함수의 진행에 있어서 함수 내에서 특정 원소를 선택한 것으로 가정하고, 다시 재귀함수를 호출하여 해당 상태를 유지한 채로 선택을 진행하며, 해당 재귀함수의 진행 사이클이 종료되어 빠져나온 경우 다시 해당 원소의 선택을 해제하여 반복문을 돌아 모든 경우를 계산하는 것이다.

이 문제에서도 주어진 조건이 주어진 친구 여부 쌍을 바탕으로 학생들이 짝을 이루는 모든 경우를 계산하여야 하므로, 위와 같은 방식으로 재귀함수를 응용하여 문제를 풀어야 할 것이다.

static int CountParing(boolean[] taken, boolean[][] areFriends) {
	boolean finished = true;
	for (int i = 0; i < taken.length; i++) {
		if (taken[i] == false)
			finished = false;
	}
	if (finished == true)
			return 1;
	int ret = 0;
	for (int i = 0; i < taken.length; i++) {
		for (int j = 0; j < taken.length; j++) {
			if (!taken[i] && !taken[j] && areFriends[i][j]) {
				taken[i] = taken[j] = true;
				ret += CountParing(taken, areFriends);
				taken[i] = taken[j] = false;
			}

		}
	}
	return ret;
}

areFriends[a][b] : a번째 학생과 b번째 학생이 친구인지 저장하는 boolean값 2차원 배열
taken[x] : x번째 학생이 짝을 이루었는지 저장하는 boolean값 배열

재귀함수의 구성을 보면 앞서 예시로 든 원소 선택하기 재귀함수처럼, 이중 반복문을 통해 i번째 학생과 j번째 학생이 아직 짝을 이루지 않았고, 서로 친구일 경우 짝을 이룬 상태로 설정하고, 재귀함수를 호출하여 반복한 횟수를 저장하는 ret 변수를 통해 반복값을 저장하며, 다시 i번째 학생과 j번째 학생이 짝을 이루지 않은 상태로 설정하여 반복문을 도는 형태이다.

언뜻 보기엔 완벽하고 정답인 것 같지만, 이 함수는 다음과 같은 오류를 범하고 있다.

같은 학생을 두 번 짝지어 준다. ( 0,1과 1,0을 별개로 취급)
다른 순서로 학생을 짝지은 경우 다른 경우로 인식한다. (0,1 후 2,3을 짝지은 것과 2,3 후 0,1을 짝지은 것을 별개로 취급)

위 두 문제를 해결하기 위해, 재귀함수에서 순서의 개념을 도입한다. 학생들의 짝을 이룰때, 현재 남아 있는 학생들(짝을 이루지 않은 학생)중 가장앞번호의 학생부터 짝을 이루는 것으로 강제한다. 예를 들어, (2,5), (0,1) 순서로는 짝을 이룰 수 없고, (0,1) , (2,5) 순서로 짝을 이루게 하는 형태이다.

static int CountParing(boolean[] taken, boolean[][] areFriends) {
	int firstFree = -1;
	for (int i = 0; i < taken.length; i++) {
		if (taken[i] == false) {
			firstFree = i;
			break;
		}
	}
	if (firstFree == -1)
		return 1;
	int ret = 0;
	for (int i = firstFree + 1; i < taken.length; i++) {
		if (!taken[i] && areFriends[i][firstFree]) {
			taken[i] = taken[firstFree] = true;
			ret += CountParing(taken, areFriends);
			taken[i] = taken[firstFree] = false;
		}
	}
	return ret;
}

firstFree 변수를 설정하여, taken 배열을 돌아 아직 짝을 이루지 않은 가장 앞번호의 위치를 찾고, 해당 위치의 다음부터 반복문을 돌아서 firstFree와, 반복문 속 i번째, 즉 firstFree 이후의 순서상에 존재하는 짝을 찾아 짝을 지어주는 형태로 변형하였다. 이 방식대로 풀 경우 앞서 발생한 두가지 문제를 모두 해결할 수 있다.

Menu

문제

풀이

N개의 원소 중 M개의 원소 선택