문제

[알고스팟 - 소풍]

풀이

1. dfs (재귀)

#include <iostream>
#include <vector>
using namespace std;

bool inExplored(vector<pair<int, int>>& explored, pair<int, int>& pair) {
	for(auto exp : explored) {
		if(pair.first == exp.first or pair.first == exp.second or pair.second == exp.first or pair.second == exp.second)
			return true;
	}
	return false;
}


int solution(const vector<pair<int, int>>& pairs, vector<pair<int, int>>& explored, int n, int index=0,  int count=0) {
	if(n/2 == explored.size()){
		return count + 1;
	}
	
	for(; index < pairs.size(); index++) {
		pair<int, int> pair = pairs[index];

		if(not inExplored(explored, pair)) {
			explored.push_back(pair);
			count = solution(pairs, explored, n, index+1, count);
			explored.pop_back();	
		}	

	}

	return count;
}

int main() {
	int C;
	cin >> C;

	for(int i=0; i < C; i++) {
		int n;
		cin >> n;

		int m;
		cin >> m;

		vector<pair<int, int>> pairs = {};

		for(int i=0; i < m; i++) {
			int a, b;
			cin >> a;
			cin >> b;

			pair<int, int> pair(a, b);
			pairs.push_back(pair);
				
		}

		vector<pair<int, int>> explored = {};

		cout << solution(pairs, explored, n) << endl;
		
	}

	
	return 0;

}

[dfs 포스팅]

깊이 우선 탐색의 방법으로 재귀하며 정답을 도출하였다.

결과는 8 m/s 의 수행시간으로 정답.