12958번 - 단순 사이클의 개수

그래프 G에서 길이 L ≥ 3인 단순 사이클이란 정점 순열 (v₀, v₁, ..., v_L-1)을 말한다. 이때, v₀, v₁, ..., v_L-1은 모두 같지 않아야 하고, 모든 0 ≤ i ≤ L-1에 대해서, v_i와 v_i+1 mod L 를 연결하는 간선이 G에 있어야 한다.

두 트리를 연결해서 그래프를 만들 수 있다. 트리의 연결은 다음과 같은 과정을 거친다.

먼저, 두 트리는 모두 N개의 정점으로 이루어져 있고, 정점은 0번부터 N-1번까지 번호가 매겨져 있다. 이제, 0부터 N-1까지 수로 이루어진 순열 P를 하나 만든다. 그 다음, 모든 0 ≤ i ≤ N-1에 대해서, 첫 번째 트리에서 i번 정점과, 두 번째 트리에서 P[i]번째 정점을 연결한다.

이렇게 만든 그래프에서 원래 첫 번째 트리에 있던 i번 정점은 A_i로, 두 번째 트리에 있던 i번 정점은 B_i로 나타낸다.

P를 어떻게 고르냐에 따라서, 나올 수 있는 길이가 K인 단순 사이클의 개수는 달라진다.

두 트리와 K가 주어졌을 때, P를 길이가 K인 단순 사이클의 개수가 가장 크게 되게 골랐을 때, 단순 사이클의 개수를 구하는 프로그램을 작성하시오.

두 단순 사이클 X와 Y가 있을 때, X를 쉬프트하거나, 뒤집어서 쉬프트했을 때, Y를 만들 수 있다면, X와 Y는 같은 사이클이다. 예를 들어, (1, 2, 3, 4), (2, 3, 4, 1), (3, 2, 1, 4)는 모두 같은 사이클이다.

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 9, 3 ≤ K ≤ 7)

둘째 줄부터 N개의 줄에 트리 1의 정보가, 다음 N개의 줄에 트리 2의 정보가 주어진다. 트리의 정보는 인접 행렬로 주어지며, '-'인 경우에는 간선이 없음, 'X'인 경우는 간선이 있음을 나타낸다.

첫째 줄에 입력으로 주어진 두 트리를 연결했을 때 나올 수 있는 길이가 K인 단순 사이클의 최대 개수를 출력한다.

예제 1의 경우에 두 방법으로 합칠 수 있고, 길이가 4인 단순 사이클은 1개이다.

예제 2의 경우에는 총 6가지 방법으로 합칠 수 있다.

가장 위에 있는 두 그래프를 제외하면 길이가 5인 단순 사이클을 총 2개씩 갖는다.

예제 3은 예제 2와 같은 그래프이다. 길이가 3인 사이클은 없다.

예제 4의 경우에 정답 P = [0, 3, 2, 1, 4] 이다. 길이가 6인 단순 사이클 5개를 찾을 수 있다.

• A0, A1, A4, B4, B1, B0
• A0, A1, A2, B2, B1, B0
• A1, A2, B2, B1, B0, B3
• A1, A2, B2, B1, B4, A4
• A1, A4, B4, B1, B0, B3