[BOJ 19276 // C++] Magic Trick

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 19276번 문제인 Magic Trick이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/19276

 

주어진 원순열을 하나의 사이클로 구성된 그래프로 생각하자. 이 때 각각의 주어지는 세 점의 묶음은 어떤 한 정점과 그와 인접한 두 정점들로 이루어져 있으므로, 각 묶음에서 두 정점을 고르면 그래프상에서의 두 점 사이의 거리가 1 또는 2가 됨을 알 수 있다.

 

추가로, $n$이 4보다 큰 경우 각 묶음으로부터 얻을 수 있는 두 정점 선택의 쌍을 모두 모으면 거리가 1인 쌍은 두 번씩 등장하며 2인 쌍은 한 번씩 등장하게 됨을 관찰할 수 있다. 이를 이용하면 주어진 원순열을 구성하는 에지가 무엇인지를 map 등을 이용해 판별할 수 있고, 이를 이용해 문제를 해결할 수 있다.

 

$n=3$인 경우는 가능한 원순열이 한 종류밖에 없으므로 자명한 답을 보인다. 또한 $n=4$인 경우 네 수 가운데 하나씩 빠진 묶음 4개가 항상 등장해야 하므로 입력이 유일하고, 이 경우 또한 자명한 답을 보인다. (한편, 아래의 코드는 이 경우들에 대해서도 제대로 된 답을 도출한다.)

 

아래는 제출한 소스코드이다.

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

int N;
vector<int> G[200001];
map<pair<int, int>, int> mp;
bool visited[200001];

void dfs(int cur) {
	cout << cur << ' ';
	visited[cur] = 1;
	for (auto &nxt:G[cur]) {
		if (visited[nxt]) continue;
		dfs(nxt);
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int k = 0; k < N; k++) {
		int x, y, z; cin >> x >> y >> z;
		mp[make_pair(min(x, y), max(x, y))]++;
		mp[make_pair(min(y, z), max(y, z))]++;
		mp[make_pair(min(z, x), max(z, x))]++;
	}

	for (auto &p:mp) {
		if (p.second > 1) G[p.first.first].emplace_back(p.first.second), G[p.first.second].emplace_back(p.first.first);
	}

	dfs(1);
}