PICNIC

 
#include <iostream>
#include <vector>

using namespace std;

const int MAX_BUFFER_SIZE = 1024;

int studentCnt = 0, pairCnt = 0;
bool areFriend[10][10] = { false, };

int makePairing(bool done[10]);
void splitStringWithDelim(char* source, vector<int> &result, char delim, int maxSize);

int main()
{
	int caseNum = 0;
	char areFriendInput[MAX_BUFFER_SIZE];
	vector<int> areFriendInputParsed;
	bool done[10] = { false, };

	cin >> caseNum;
	
	for (int caseIter = 0; caseIter < caseNum; caseIter++)
	{
		/* Clear variables */
		for (auto &d : done)
		{
			d = false;
		}

		for (auto &fr : areFriend)
		{
			for (auto &f : fr)
			{
				f = false;
			}
		}

		areFriendInputParsed.clear();

		/* get input - studentCnt, relationShipResult */
		cin >> studentCnt >> pairCnt;
		cin.ignore();
		cin.getline(areFriendInput, MAX_BUFFER_SIZE);
		splitStringWithDelim(areFriendInput, areFriendInputParsed, ' ', MAX_BUFFER_SIZE);

		/* make friendShip array */
		for (int resultNum = 0; resultNum < areFriendInputParsed.size(); resultNum++)
		{
			if (resultNum % 2 == 1) continue;

			int studentElemFirst = areFriendInputParsed[resultNum];
			int studentElemSecond = areFriendInputParsed[resultNum + 1];

			areFriend[studentElemFirst][studentElemSecond] = true;
			areFriend[studentElemSecond][studentElemFirst] = true;
		}

		/* get result */
		cout << makePairing(done) << endl;
	}
}

int makePairing(bool done[10])
{
	int first = 0;
	for (first = 0; first < studentCnt; first++)
		if (done[first] == false) break;
	if (first == studentCnt) return 1;

	int ret = 0;
	for (int pair = first + 1; pair < studentCnt; pair++)
	{
		if (done[pair] == false && areFriend[first][pair])
		{
			done[first] = done[pair] = true;
			ret += makePairing(done);
			done[first] = done[pair] = false;
		}
	}

	return ret;
}


void splitStringWithDelim(char* source, vector<int> &result, char delim, int maxSize)
{
	char *buf = new char[256]();
	int sourceIdx = 0;
	int bufIdx = 0;

	for (sourceIdx = 0; sourceIdx < maxSize; sourceIdx++)
	{
		if (source[sourceIdx] == delim || source[sourceIdx] == '\0')
		{
			// copy buffered string to result array
			buf[bufIdx] = '\0';
			result.push_back(atoi(buf));

			// if source string is end, break for loop
			if (source[sourceIdx] == '\0') break;

			bufIdx = 0;
		}
		else
		{
			buf[bufIdx] = source[sourceIdx];
			bufIdx++;
		}
	}

	return;
}
 

  코드를 짜는 동안 C++ 의 Shallow Copy 개념이 흔들렸었다. 배열을 함수의 파라미터로 넘겨줄 때 포인터(*)로 넘겨주거나 레퍼런스(&) 로 넘겨주면 Deep Copy가 되고, 그냥 변수를 넘겨주면 Shallow Copy 가 되는 게 일반적이다. 그런데 Shallow Copy 를 기대하고 변수를 넘겨 주었었는데 Deep Copy 처럼 동작을 했다. 지금 생각해 보면 애초에 Shallow Copy, Deep Copy 의 문제가 아니었다. 단지 재귀 호출을 진행하면서 done 의 값이 변했다가 원상태로 돌아오는 메커니즘을 반복할 뿐이었다...

"done[first] = done[pair] = true;" 이후에 "done[first] = done[pair] = false;" 를 해 주면서 한 depth 내려갔다가 다시 올라올 떄의 처리를 해주는 것 뿐이었다. 또 시간을 잡아 먹었던 것은 각 case 마다 루프를 돌 때 areFriend 배열을 초기화 하지 않아서 답이 이상하게 나왔었다. 답이 이상하게 나오는 case를 따로 빼내어서 프로그램을 실행시켰는데 정상적인 답이 나오는 것을 보고서야 내가 초기화를 놓쳤음을 알게 되었다..

  Input 을 delim 기준으로 나누는 함수는 내가 예전에 만들었던 splitStringWithDelim() 함수를 가져다가 사용하였다.

picnicInput.txt

picnicOutput.txt