[알고리즘] - 소풍
문제
풀이
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;
}
#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;
}
깊이 우선 탐색의 방법으로 재귀하며 정답을 도출하였다.
결과는 8 m/s 의 수행시간으로 정답.
Author And Source
이 문제에 관하여([알고리즘] - 소풍), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sjoonb/알고리즘-소풍저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)