알고스팟 - 소풍

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;
int n, m;
int tcase;
bool arefriends[10][10];
int dfs(bool selected[10]) {
	int firstfree = -1;
	for (int i = 0;i < n;i++) {
		if (!selected[i]) {
			firstfree = i;// 아직 골라지지 않은 사람의 인덱스를 저장하고 break
			break;
		}
	}
	
	if (firstfree == -1) return 1;
	int ret = 0;
	for (int j = firstfree + 1; j < n;j++) {
		if (!selected[j] && arefriends[firstfree][j]) {
			selected[firstfree] = selected[j] = true;
			ret += dfs(selected);
			selected[firstfree] = selected[j] = false;// 다른 경우의 수도 찾아야하기 때문에 짝 해제
		}
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> tcase; // 테스트 케이스
	bool selected[10];
	for (int i = 0;i < tcase;i++) {

		cin >> n >> m;

		memset(arefriends, false, sizeof(arefriends));
		memset(selected, false, sizeof(selected));

		for (int j = 0;j < m;j++) {//쌍의 갯수만큼
			int o = 0;
			int p = 0;
			cin >> o >> p;
            //짝의 원소순서가 바뀌어도 결국 같은 짝이기 때문에 둘다 true로 기입
			arefriends[o][p] = arefriends[p][o] = true;
		}
		cout << dfs(selected)<<"\n";
		//v.clear();
	}


	return 0;
}

 책에 있는 풀이와는 좀 다르게 접근을 했었는데 실패했다.

이유는 부끄럽지만 그냥 문제를 잘못 이해했었다. 

한참을 시간낭비 하다가 내가 문제를 잘못 이해했는걸 뒤늦게 이해하고

책을 다시 읽고  풀었더니 정답이 나왔다.

 

언제나 문제를 똑바로 읽자

 

이 문제의 키 포인트는 (0,1) , (2,3) 을 세는 방법과 (2,3) ,(0,1) 을 중복해서 세지말고 같은걸로 취급하도록 해줘야하는거다.

 

이럴때 흔히 사용하는 방법은 항장 특정 형태를 갖는 답만을 세는 방법이다.

예를들어 같은 답 중에서 사전순으로 가장 먼저 오는 답 하나만을 세는 방법이다.

(2,3),(0,1) 이나 (1,0),(2,3) 은 세지 않지만 (0,1),(2,3) 은 세는것 

 

중복되지 않도록 고르는 문제는 다른 사이트의 문제에서도 많이 풀어봤지만 중복되지 않는 쌍을 처리하는건 처음 접해봤다. 

전체적인 로직은 기존 문제들과 비슷하지만

선택을 한번에 2명씩 한다는 점과 

이미 골랐던 정보인지만 체크하는게 아니라 친구인지도 체크 해줘야 한다는 점이 다르다.

 

문제출처 : https://www.algospot.com/judge/problem/read/PICNIC