[algospot] PICNIC

소풍 (ID : PICNIC)

---

내 풀이 코드 (틀린 버전)

#include <iostream>
#include <fstream>

using namespace std;

bool areFriends[50][10][10] = {0};
int n;

int countPairings(bool isPaired[10]){
	// 기저 사례 : 모든 학생이 짝을 찾았으면 한 가지 방법을 찾았으니 종료한다.
		bool isFinished = true;
		for(int i = 0 ; i < n; i ++) if(!isPaired[i]) isFinished = false;
		if(isFinished) return 1;
	
	int ret = 0;
	for(int i = 0 ; i < n ; i++)
		for(int j = 0; j < n; j++){
			if(!isPaired[i] && !isPaired[j] && areFriends[i][j]){
				isPaired[i] = isPaired[j] = true;
				ret += countPairings(isPaired);
				isPaired[i] = isPaired[j] = false;
			}
		}
	return ret;
}


int main(){
	int C, studentNum[50], pairNum[50];
	int pairArr[50][90];
	int result[50];
	
	// 파일 입출력을 위함.
	std::ifstream readFile;
	readFile.open("./picnic.txt");
	
	readFile >> C; // cin >> C;
	readFile.ignore(); // cin.ignore();

	for(int c = 0; c < C; c++){ // 테스트 케이스 개수 C 만큼 반복
		readFile >> studentNum[c];
		readFile >> pairNum[c];
		
		readFile.ignore();
		
		for(int i = 0; i < 2 * pairNum[c]; i++){
			readFile >> pairArr[c][i];
		}
		readFile.ignore();
	}
	
	for(int c = 0; c < C; c++){ // 테스트 케이스 개수 C 만큼 반복
		bool isPaired[10] = {false};		
		// 입력으로 받은 pair 를 2차원 배열 areFriends 에 정리해보자
		for(int x = 0; x < 2 * pairNum[c] - 1; x++){
			areFriends[c][pairArr[c][x]][pairArr[c][x+1]] = true;
		}
		n = studentNum[c];
		result[c] = countPairings(isPaired);
	}
	for(int c = 0; c < C; c++){ // 테스트 케이스 개수 C 만큼 반복
		cout << result[c] << endl;
	}
	
}

이 코드의 문제점은 무엇일까. 재귀문을 잘 살펴보면 답을 중복으로 세는 상황이 발생한 것을 알 수 있다. 이 상황을 해결하기 위해 선택할 수 있는 좋은 방법은 항상 특정 형태를 갖는 답만을 세는 것이다. 흔히 사용하는 방법으로는 답 중에서 사전순으로 가장 먼저 오는 답 하나만을 세는 것이다. 이 방법을 참고해서, 이 문제에서는 남은 학생들 중 가장 번호가 빠른 학생의 짝을 찾아주도록 하여 중복으로 세는 문제를 해결하였다.

 

#include <iostream>
#include <fstream>

using namespace std;

bool areFriends[50][10][10] = {0};
int n;

int countPairings(bool isPaired[10], int testNum){
	// 가장 번호가 빠른, 짝지어지지 않은 학생을 찾는다.
	int firstNotPaired = -1;
	for(int i = 0; i < n; i++){
		if(!isPaired[i]) {
			firstNotPaired = i;
			break;
		}
	}
	
	// 기저 사례 : firstNotPaired 가 그대로 -1 이라면 가장 번호가 빠른 짝지어지지 않은 학생이 없는 것이므로, 모든 학생이 짝을 찾은 것이다. 종료한다.
	if(firstNotPaired == -1) {
		return 1;
	}
	
	int ret = 0;
		for(int pairWith = firstNotPaired + 1; pairWith < n; ++pairWith){
			if(!isPaired[pairWith] && areFriends[testNum][firstNotPaired][pairWith]){
				isPaired[firstNotPaired] = isPaired[pairWith] = true;
				ret += countPairings(isPaired, testNum);
				isPaired[firstNotPaired] = isPaired[pairWith] = false;
			}
		}
	return ret;
}


int main(){
	int C, studentNum[50], pairNum[50];
	int pairArr[50][90];
	int result[50];
	
	// 파일 입출력을 위함.
	std::ifstream readFile;
	readFile.open("./picnic.txt");
	
	readFile >> C; // cin >> C;
	readFile.ignore(); // cin.ignore();

	for(int c = 0; c < C; c++){ // 테스트 케이스 개수 C 만큼 반복
		readFile >> studentNum[c];
		readFile >> pairNum[c];
		
		readFile.ignore();
		
		for(int i = 0; i < 2 * pairNum[c]; i++){
			readFile >> pairArr[c][i];
		}
		readFile.ignore();
	}
	
	for(int c = 0; c < C; c++){ // 테스트 케이스 개수 C 만큼 반복
		bool isPaired[10] = {false};		
		// 입력으로 받은 pair 를 2차원 배열 areFriends 에 정리해보자
		for(int x = 0; x < 2 * pairNum[c] - 1; x = x + 2){
			areFriends[c][pairArr[c][x]][pairArr[c][x+1]] = true;
			areFriends[c][pairArr[c][x+1]][pairArr[c][x]] = true;
		}
		n = studentNum[c];
		result[c] = countPairings(isPaired, c);
		cout << endl;
	}
	for(int c = 0; c < C; c++){ // 테스트 케이스 개수 C 만큼 반복
		cout << result[c] << endl;
	}
	
}

문제의 간단한 해법

어떠한 방식 / 깨달음 으로 접근했는지 & 사용한 문제 해결 전략

: 무식하게 풀기 방식을 적용해보았을 때, 이 문제에 가장 적합한 방법은 반복 / 재귀를 통해 가능한 한 모든 짝짓기의 경우를 고려해보는 것이었다. 하지만, 이러한 방식으로 접근했을 때의 문제점은 같은 방법을 중복하여 세는 것이었다. 중복으로 세는 문제는 굉장히 흔하게 마주하게 되는, 이 상황을 해결하기 위해 선택할 수 있는 좋은 방법은 항상 특정 형태를 갖는 답만을 세는 것이다. ( 02.문제 해결 개관 9번) 

오답 원인

: 중복으로 답을 세는 상황을 마주하였을 때, 항상 특정 형태를 갖는 답만을 세는 전략을 써볼 수 있었다. 하지만, 결과적으로 완전히 오류를 해결하지는 못하였는데 예제의 3번째 예제가 15가 나온다. 디버깅을 통해서 따라가보았지만 재귀 함수를 머릿속으로 따라가는 것은 매우 복잡한듯 하다. 왜 이런 중복이 나오는 걸까? 

고찰

몇 시간의 고민 끝에 나는 오류 원인을 찾아냈다. 우리가 입력한 areFriends[테스트 개수][10][10] 을 잘못 쓰고 있었다는 점이다.  if(!isPaired[pairWith] && areFriends[testNum][firstNotPaired][pairWith])

라는 조건문이 있다. 처음에 나는 areFriends[firstNotPaired][pairWith] 으로 써서, 3차원 으로 선언한 배열을 2차원으로 쓰고있었다. 컴파일러가 잡아주지 못한 오타가 발생한 것이다. 조건문 상에서는 false 가 아닌 값이 들어왔으므로 무조건 참으로 받아들인 것이다. 이러한 오류를 찾아내는데에는 디버깅이 큰 몫을 해주었다. 코드 진행에 따른 변수값의 변화를 살펴보며, areFriends 배열이, 처음 의도했던 것처럼 역할을 해주지 못한다는 것을 깨달아 그 부분을 집중적으로 살펴보았기 때문이다. 

새로이 배운 점

: 재귀함수를 오랜만에 써보면서, 재귀 함수의 작동 방식에 대해서 약간 더 익숙해질 수 있었다. 답을 중복하여 세는 경우에는, 특정한 형태만을 정답으로 인정하는 방식을 이용한다는 것을 이용해보았는데, 개관에서 말로만 보다가 실제로 마주해보니 생각보다 더 강력한 방법이라는 것을 깨달았다.

:

isPaired[firstNotPaired] = isPaired[pairWith] = true;
ret += countPairings(isPaired, testNum);
isPaired[firstNotPaired] = isPaired[pairWith] = false;

나는 이 부분이 재귀함수의 핵심이라고 생각한다. 코드를 보자마자 문제 풀이의 과정이 보이는 것은 아니지만 예제를 하나 두고서 흐름을 따라가보면 놀라울만큼 정확하다. 재귀함수는 이러한 간결함이 좋은 것 같다. 하지만, 그만큼 세밀한 구현이 필요하다는 것을 느꼈다. 어떻게 하면 바로 이렇게 간결한 풀이를 생각해낼 수 있을까..

또한, 기저 사례를 설정하는 것이 매우 중요하다는 것을 느꼈다. 언제 이 재귀를 끝낼 것인가. 무엇을 return 할 것인가. 이 문제를 어떻게 분할 할 것인가. 이런 것들을 결정하는 것은 재귀 함수의 main logic 을 정하는 것 만큼이나 중요하다.

완전 탐색 레시피

• 최대 크기의 입력을 가정했을 때 답의 개수를 계산하고 이들을 모두 제한 시간 안에 생성할 수 있을지를 가늠한다.
• 가능한 모든 답의 후보를 만드는 과정을 여러 개의 선택으로 나눈다.
• 그 중 하나의 조각을 선택해 답의 일부를 만들고, 나머지 답을 재귀 호출을 통해 완성한다.
• 조각이 하나 밖에 없거나, 혹은 하나도 남지 않은 경우에는 답을 생성한 것이므로 이것을 기저 사례로 설정한다.

간결한 코드를 작성하는 팁 

 : 입력이 잘못되거나 범위에서 벗어나는 경우도 기저 사례로 선택해서 맨 처음에 처리하는 것이다.

다른 사람(책)의 코드를 보고 비교

: