[BOJ 1073] 도미노

 

[문제]

 

www.acmicpc.net/problem/1073

1073번: 도미노

 

[난이도]

 

- Platinum 4 (solved.ac 20.11.06 기준)

 

 

[필요 개념]

 

- 오일러 회로 (Eulerian Circuit)

 

 

[풀이]

 

(이 블로그를 참고했습니다. wootool.tistory.com/46)

 

이 문제는 코드나 풀이가 상당히 간단하지만, 생각해내기가 쉽지 않은 문제이다. 

 

우선 오일러 회로 개념에 대한 이해가 필요하다. 

짧게 설명하면, 무향 그래프에서 그래프의 시작점으로부터 출발해서 모든 간선을 한 번씩만 지나가면서 다시 시작점으로 돌아올 수 있기 위해서는 모든 점의 차수가 짝수가 되어야 한다. 

여기서 차수는 각 점에 연결된 간선의 개수이다. 

 

따라서 이 문제에서는 각 조각이 간선의 역할을 하게 되고, 정점은 0부터 9까지의 수가 될 것이다.

차수가 홀수인 점이 하나라도 있으면 답은 0이 된다. 

 

한 정점이 어떤 사이클에 포함된다면, 해당 정점으로 들어오는 간선 1개, 다시 밖으로 나가는 간선 1개가 필요하게 된다. 

이를 하나의 쌍으로 생각하면, 두 사이클이 같다는 의미는 사이클을 구성하는 쌍들이 모두 같다는 의미이다. 

따라서 각 정점별로 만들어 질 수 있는 쌍의 개수를 모두 곱하면 만들어질 수 있는 모든 사이클 컬렉션의 개수가 된다. 

 

예를 들어서 한 정점에 연결된 간선이 6개라면, (6C2 x 4C2 x 2C2)/3! 이 만들어질 수 있는 쌍의 개수이다. 

이를 일반화하면 'dp[n] = 간선이 n개일 때 만들어질 수 있는 쌍의 개수'라고 할 때, 

dp[n] = (n-1) * dp[n-2] 를 만족한다. 

한 간선을 정한 뒤, 해당 간선과 연결된 간선의 종류는 n-1가지이고, 선택된 두 간선을 제외하면 n-2개의 간선에서 쌍을 만드는 경우와 같기 때문이다. 

 

 

[소스 코드]

 

#include<bits/stdc++.h>
#define FOR(i, j, k) for(int i = j; i<=k; i++)
using namespace std;

using ll = long long;

int deg[10];
int dp[10];
int main(void) {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	int N; cin >> N;
	FOR(i, 1, N) {
		int a; cin >> a;
		deg[a / 10]++;
		deg[a % 10]++;
	}
	dp[0] = 1;
	for (int i = 2; i <= 8; i += 2) {
		dp[i] = (i - 1)*dp[i - 2];
	}
	ll ans = 1;
	for (int i = 0; i <= 9; i++) {
		ans *= dp[deg[i]];
	}
	cout << ans;
}