개인적으로 Recursive 함수를 많이 사용하는 편이라고 생각했다. 하지만, 항상 사용만 했지 한 번도 제대로 이해해 보려고 했던 적은 없는 것 같다. “프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략” 책을 읽으면서 for Loop과 Recursive 함수를 같이 사용하여 가능한 모든 조합의 수를 찾는 방법을 아주 쉽게 구현할 수 있어서 짧게 정리해보았다. 아래 코드는 책에서 작성된 Pseudocode 코드를 C로 다시 작성한 코드이다. 아래 코드는 PICNIC이라는 문제를 풀기 위한 코드이다. 문제는 서로 친하다고 생각하는 학생들만 짝을 지어 줄 때 가능한 학생의 조합을 찾는 문제이다. 아래 출처 1에서 관련 문제를 확인 할 수 있다.
#define NumStudent 10 #define True 1 #define False 0 int totalStudent; int relationship[NumStudent][NumStudent]; int studentList[NumStudent]; int numPossibleGroup() { //MK: 총 가능한 Combination 수 int returnValue = 0; int firstStudent = -1; //MK: 가장 앞 순서 부터 검색을 하기 위해서 제일 처음 가능한 학생 찾기 for (int i = 0; i < totalStudent; i++) { if (studentList[i] == False) { firstStudent = i; break; } } //MK: 모든 학생이 친구를 찾았기 때문에 함수 종료 if (firstStudent == -1) { return True; } //MK: 모든 가능한 Combination을 찾기 위해 Recursive 함수 호출 for (int i = firstStudent + 1; i < totalStudent; i++) { if (studentList[i] == False && relationship[firstStudent][i] == True) { //MK: 짝이 된 친구들을 표시함 studentList[i] = True; studentList[firstStudent] = True; //MK: Recursive 함수 호출 returnValue += numPossibleGroup(); //MK: 짝이 된 친구들을 Free하고 다시 가능한 combination 검색 studentList[i] = False; studentList[firstStudent] = False; } } return returnValue; }
numPossibleGroup() 함수는 List의 True, False 값을 이용하여 모든 가능한 조합의 수를 찾는 함수이다. numPossibleGroup() 함수 안의 for Loop은 현재의 가능한 Sub-Combination을 찾기 위해서 현재 짝이 된 2학생 (List Index)의 값에 True로 설정한다. 그리고 현재 짝이 된 학생을 제외한 모든 가능한 조합의 수를 찾기 위해 다시 numPossibleGroup() 함수를 호출한다. 이 부분에서 Recursive 함수가 된다. 현재 짝이 된 학생을 제외한 모든 조합의 수를 찾은 후 현재 함수로 다시 돌아오면, 처음에 짝이 된 2학생 (List Index)의 값을 다시 False로 세팅한다. 그리고 다시 새로운 짝을 찾아서 조합을 계속 계산하다.
그림 1: Recursive 함수 동작 순서 정리
위 그림은 numPossibleGroup() 함수가 호출되는 순서를 정리해보았다. List (학생 번호)의 값이 0이면 False이고, List 값이 1이면 True이다. True는 해당 학생이 짝을 찾았다는 의미이다. 위 예제는 모든 학생이 친구가 될 수 있다고 가정을 한 경우이다.
순서 설명
- 가장 먼저 #0과 #1학생이 짝이 된다. (Func #1)
- 그리고 새로운 numPossibleGroup() 함수를 호출한다. (Func #2)
- Func #2에서 #2와 #3학생이 짝이 된다.
- 다시 새로운 numPossibleGroup() 함수를 호출한다. (Func #3)
- Func #3에서 #5와 #6학생이 짝이 된다. 모든 가능한 조합의 수를 찾았기 때문에 함수를 종료한다. 실제로 여기서 numPossibleGroup() 함수를 한 번 더 호출한다. 다음 호출된 함수의 if (firstStudent == -1) { return True; } 라인에서 종료되어서 현재 함수로 돌아온다.
- Func #3에서 #5와 #6학생이 짝을 다시 헤어지게 한다. 해당 학생 번호에 False로 값으로 Reset 한다. (Func #3 종료)
- Func #2에서 #2와 #3학생들이 짝이 되지 않은 경우를 탐색하기 위해 #2와 #3의 Reset 한다.
- Func #2에서 #2와 #4학생이 짝이 된다.
- 다시 새로운 numPossibleGroup() 함수를 호출하여 가능한 조합을 다시 탐색한다.
위의 순서대로 계속 반복을 하다 보면 모든 가능한 조합의 수를 찾게 된다. 위 코드는 중복되는 경우의 수를 제거하기 위해서 절대로 앞 번호를 가진 학생과는 짝이 될 수 없도록 작성하였다. numPossibleGroup()을 호출하기 전에 List의 True, False를 사용하는 모든 가능한 조합의 수를 찾는 방법을 알지 못하였던 부분이라 간단하게 정리해보았다.
출처
- https://algospot.com/judge/problem/read/PICNIC
- 프로그래밍 대회에서 배우는 알고리즘 문제해결 전략 (구종만)