Picnic (소풍)

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

 

단순하게 완전탐색으로 모든 경우의 수를 탐색하면 되는 문제. 탐색 로직자체보다는 재귀를 이용하여 구현하는 부분이 어려웠다. 주어진 입력이 매우 다양하고 특히나 입력이 몇 글자나 주어지는지 알 수 없기때문에(공백이 입력으로 들어오는 Case도 존재함) 입출력 data를 신중하게 다뤄줘야했다. 특히 오류를 최대한 제어하기위해서는 문제에서 주어진 입력들의 최대, 최소값의 범위가 어떻게 되는지 유심히 봐야겠다는 걸 느꼈다.

 

재귀함수

int picnic(vector<vector<int> map, vector<int> usingNum)

에 대해서 간단하게 설명하자면

종료 시점 : usingNum(이미 짝을 찾은 사람의 인덱스)이 Max가 될 때 카운트를 올리면서 함수가 종료

재귀 및 반복 : usingNum에 포함되지 않은 나머지 사람들(짝을 찾지 못한 사람들)을 기준으로 관계도 map을 참조하여 usingNum에 포함시키면서 picnic을 재귀 실행. 위 작업을 남은 사람들의 관계도 map의 횟수만큼 반복해야한다.

기억할만한 요소

주어진 입력을 가공해서 특정 자료형태로 저장해야되는 부분이 있는데 입력은 각 요소들이 띄어쓰기로 구분되어 한번에 주어진다. 따라서 띄어쓰기를 기준으로 이 요소들을 하나하나 구별해서 특정 자료형태에 맞게 다시 가공해주는 부분을 구현해줘야한다. 이 부분이 은근 시간이 걸렸다.

c++ or c에서 특정 문자열을 구분자를 기준으로 잘라주는 함수로는 strtok()가 있다.

해당 함수는 특정 문자열을 받았을 때 해당 문자열에서 구분자를 '\0'으로 치환하고 치환한 '\0'와 함께 앞부분에 있는 문자열을 가르키는 포인터를 리턴한다.

이후 함수를 계속 호출하면 이 과정을 더 이상 구분자가 없을 때까지 반복하고 더 이상 리턴할 data가 없을때 NULL 값을 리턴한다.

#include <cstring>
char* strtok(char* str, char* delimiters); 

[strtok함수 관련 참고한 곳] https://blockdmask.tistory.com/382

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int picnic(vector<vector<int>> &friends, vector<int> & usingNum) {
	int count = 0;
	int index = friends.size() - usingNum.size();
	if (index == 0) return ++count;
	
	for (int i = 0; i < friends.size(); i++) {
		bool pass = false;
		for (int j = 0; j < usingNum.size(); j++) {
			if (usingNum[j] == i) {pass = true; break;}
		}
		if (pass) continue;

		for (auto iter = friends[i].begin(); iter != friends[i].end(); iter++) {
			bool pass = false;
			for (int j = 0; j < usingNum.size(); j++) {
				if (usingNum[j] == *iter) { pass = true; break; }
			}
			if (pass) continue;

			usingNum.push_back(i);
			usingNum.push_back(*iter);
			count += picnic(friends, usingNum);
			usingNum.pop_back();
			usingNum.pop_back();
		}
		return count;
	}
}

int main() {
	int testcase;
	scanf("%d", &testcase);

	for (int i = 0; i < testcase; i++) {
		int n, m;
		scanf("%d %d", &n, &m);
		getchar();
		
		char pair[200];
		scanf("%[^\n]", pair);
		char* temp_pair = strtok(pair, " ");
		vector<vector<int>> friends(n);
		while (temp_pair != NULL){
			if (m == 0)  break;
			int first = (int)*temp_pair - 48;
			temp_pair = strtok(NULL, " ");
			int second = (int)*temp_pair - 48;

			if (first < second) friends[first].push_back(second);
			else friends[second].push_back(first);
			
			temp_pair = strtok(NULL, " ");
		}
		
		vector<int> use = {};
		int count = picnic(friends, use);
		printf("%d\n", count);
	}
	return 0;
}

작성한 코드