[BOJ] 1073. 도미노

문제 링크
수 2개가 적혀있는 도미노 $N$개가 주어집니다. 각 도미노에는 0부터 9까지의 서로 다른 수가 적혀있고 $N$개의 도미노는 서로 중복 되지 않습니다. 이 때, 주어진 도미노를 전부 사용해서 만들 수 있는 서로 다른 사이클 콜렉션의 총 갯수를 구하면 됩니다.

첫번째 예제를 토대로 정리해 보겠습니다. 먼저 주어진 도미노를 토대로 아래와 같이 그래프로 모델링 하면 도미노로 만들 수 있는 사이클은 그래프의 사이클로 표현 됩니다.

즉, 사이클 콜렉션이 존재하기 위해서는 그래프로 모델링 했을 때, 각 정점의 차수가 전부 짝수여야 합니다. 각 정점에 붙은 간선은 1개 혹은 2개 이상의 사이클에 전부 포함될테고 각 정점이 어떤 사이클에 포함된다면 해당 정점에 붙어있으면서 사이클에 포함되는 간선은 들어오는 간선과 나가는 간선 쌍이 1:1 매치 되어야 하므로 짝수개의 간선이 포함됩니다. 즉, 각 정점의 차수는 전부 짝수여야 합니다.

그럼 각 정점의 차수가 모두 짝수일 때 사이클 콜렉션의 갯수를 어떻게 구해야 할까요? 아까전에 들어오는 간선과 나가는 간선 쌍이 1:1 매치 되어야 한다고 했습니다. 그 전에 아래와 같이 간선에 번호를 부여해 보겠습니다.

2번 정점에서 간선을 (1, 2), (3, 4)로 매칭해 주는 경우를 생각해 보겠습니다. 매칭이 된 시점부터 들어오는 간선에 따라 나가는 간선이 자동으로 정해 집니다. 즉, 아래와 같이 모델링 할 수 있습니다.

같은 방식으로 (1, 3), (2, 4)와 (1, 4), (2, 3)으로 매칭했을 때의 그래프는 아래와 같습니다.

보시다시피 각 연결 요소가 하나의 단순 사이클로 구성되는 그래프로 만들어집니다. 이 말은 즉, 각 정점에서 들어오는 간선과 나가는 간선을 1:1 매칭을 시켜주면 그것에 대응되는 사이클 콜렉션이 만들어지고 당연히 어떤 사이클 콜렉션이 있으면 그것에 대응되는 그래프 또한 만들 수 있습니다. 즉, 사이클 콜렉션의 갯수는 각 정점에서 들어오는 간선과 나가는 간선을 1:1 매칭 시키는 경우의 수가 됩니다.

정점의 차수가 $n$일 때, 간선 매칭의 경우의 수를 $S_{n}$이라고 하면 $S_{n}$은 아래와 같이 구할 수 있습니다.

문제 특징상 $n$이 10을 넘길일은 없으므로 Naive하게 계산해도 괜찮습니다. 혹은 아래 점화식을 활용하여 DP로 $S_{n}$을 계산한 뒤 답을 구해도 됩니다.