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;
}
작성한 코드
Author And Source
이 문제에 관하여(Picnic (소풍)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dlsghl92/Picnic-소풍저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)