시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 134 | 62 | 50 | 51.546% |
안드로이드는 스마트폰을 잠글때 패턴을 이용한다. 보통 잠근 패턴은 3×3 그리드에 노드 9개로 이루어져 있다. 상현이는 보다 더 높은 보안을 위해 아래와 같은 잠금 패턴을 제공하는 앱을 만들려고 한다.
상현이가 만들 앱의 잠금 패턴의 크기는 2×2부터 m×m까지로 다양하며, 항상 인접한 노드만 연결할 수 있다. 잠금 패턴은 그래프로 나타낼 수 있다. 아래 그림은 2×2, 3×3, 4×4 잠금 패턴을 그래프로 나타낸 것이다. 꼭짓점에 해당하는 정점은 총 3개와 연결되어 있고, 나머지 정점은 최대 8개와 연결될 수도 있다. 항상 아래 그림과 같이 인접한 점과만 연결할 수 있다.
잠금 패턴은 항상 스패닝 트리를 이루어야 한다. 스패닝 트리는 그래프 상의 간선의 집합으로, 닫힌 루프를 포함하지 않아야 한다. 또, 임의의 두 점 사이의 경로가 존재해야 하고, 모든 m2 = n개의 정점과 n-1개의 edge로 이루어져 있어야 한다. 잠금 패턴 상에서 스패닝 트리는 여러 가지 경우가 나올 수 있다.
그래프 G의 스패닝 트리의 개수를 구하기 위해 모든 정점에 번호 v1, ..., vn을 붙인다. 이제 행렬 T = [tij]를 아래와 같이 만들 수 있다.
스패닝 트리의 개수는 다음과 같이 구할 수 있다.
cofactor of aij = (-1)i+jMij
여기서 Mij는 T에서 i행과 j열을 지워서 얻은 (n-1) × (n-1) 행렬의 행렬식(determinant)이다. T의 모든 cofactor는 같은 결과를 갖는다.
예를 들어, 2×2 패턴의 행렬 T는 다음과 같다.
\[T=\begin{pmatrix} 3 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 \\ -1&-1&3&-1 \\ -1&-1&-1&3 \end{pmatrix}\]
i=1, j=1로 두고 cofator를 구해보면 아래와 같다.
\[(-1)^{1+1}M_{11} = \begin{vmatrix} 3& -1&-1 \\ -1&3&-1 \\ -1&-1&3 \end{vmatrix} = 16\]
따라서, 스패닝 트리의 개수는 16개임을 알 수 있다.
두 번째 예제로 3×3 패턴의 행렬 T는 다음과 같다.
\[T = \begin{pmatrix} 3&-1&0&-1&-1&0&0&0&0 \\ -1&5&-1&-1&-1&-1&0&0&0 \\ 0&-1&3&0&-1&-1&0&0&0 \\ -1&-1&0&5&-1&0&-1&-1&0 \\ -1&-1&-1&-1&8&-1&-1&-1&-1 \\ 0 & -1&-1&0&-1&5&0&-1&-1 \\ 0&0&0&-1&-1&0&3&-1&0 \\ 0&0&0&-1&-1&-1&-1&5&-1 \\ 0&0&0&0&-1&-1&0&-1&3 \end{pmatrix}\]
T의 모든 cofactor는 같은 결과를 갖고, 이 답이 스패닝 트리의 개수가 된다.
m×m 패턴에서 만들 수 있는 스패닝 트리의 개수를 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 N (1 ≤ N ≤ 5)가 주어진다. 다음 N개 줄에는 테스트케이스 한 줄에 하나씩 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 패턴의 크기 m이 주어진다. (2 ≤ m ≤ 6)
각 테스트 케이스마다 m×m 패턴에서 만들 수 있는 스패닝 트리의 개수를 한 줄에 하나씩 출력한다.
1 2
16
m = 2인 경우 아래와 같이 16가지 경우가 있다.
ICPC > Regionals > Asia Pacific > Thailand > 2013 ACM-ICPC Asia Phuket Regional Programming Contest A번