[Python] 9066번 금고

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

9066번: 금고

---

 

23/03/20

 

 

체감 상 플레티넘 5보다 어려웠다고 느껴졌던 문제이다. 나는 선형대수학적 지식을 이용하여 문제를 해결했다.

 

시간복잡도 상으로 더 짧게 걸리는 풀이도 있긴 하나, 결국 이 풀이 또한 내가 풀었던 방법과 본질적으로는 같은 방법으로, 이를 증명하기 위해서는 선형대수학적 지식이 수반되어야 한다.

 

때문에 이 글은 선형 대수학의 내용 중 '체'와 '벡터공간'에 대한 지식과, 연립 일차 방정식을 첨가 행렬(Argumented Matrix)로 나타내 '가우스 소거법'을 이용하여 푸는 방법을 알고 있다는 전제 하에서 쓰여짐을 밝힌다.

---

 

문제 접근 방식:

 

 

각 손잡이의 번호가 오른쪽에서 왼쪽으로, 위에서 아래로 1번부터 $N^2$번까지 매겨져있다.

 

우리는 $N$번째 손잡이의 상태는 수평 또는 수직 상태 밖에 존재하지 않음을 알 수 있다.

 

단순화를 위해, 수평 상태를 $0$, 수직 상태를 $1$로 간주해보자.

 

우리는 $N$번째 손잡이를 잡고 돌리면, 그 손잡이의 상태가 $0$이라면 $1$로, $1$이라면 $0$으로 바뀐다는 사실을 잘 알고 있다.

 

다시 말해, '손잡이를 돌리는 행위'를 '연산'으로 간주한다면, 이 연산은 짝수번 반복하면 원래대로 돌아오고, 홀수번 반복하면 반대 상태로 돌아간다.

 

이와 똑같은 구조를 가진 대수적 구조를 생각해보면, 유한 체(finite field)의 종류 중 하나인 GF(2)를 생각해볼 수 있다.

 

그러면, 손잡이를 돌리는 행위는 이 체의 덧셈(additive)연산인 $XOR$연산으로 간주할 수 있다.

 

또한, 우리가 하는 행위는 연산을 반복함으로써 행렬의 모든 원소를 0으로 만드는 행위와 같다.

 

 

이제, $X_n$이라는 미지수를 영행렬을 만들기 위해 행렬의 $n$번째 원소를 돌려야하는지에 대한 여부라고 생각하자.

(또는, 반대로 영행렬에서 주어진 행렬을 만들기 위해 행렬의 $n$번째 원소를 돌려야하는지에 대한 여부라고 생각해도 무방하다.)

 

만약 돌려야 한다면 $1$, 아니라면 $0$을 나타낸다.

 

또한, $S_n$을 주어진 행렬의 $n$번째 원소, 즉, 입력으로 주어진 손잡이의 상태라고 간주하자.

 

그러면 우리는 이를 토대로 연립 일차 방정식을 세워서, 가우스 소거법을 이용해 각 $X_n$들을 구하면 끝이다.

 

 

예시로, 예제 입력 1번의 첫번째 케이스를 살펴보자.

 

첫번째 케이스는 다음과 같이 변환할 수 있다.

 

$$\begin{matrix} 0 & 1 & 1 & 0 \\1 & 1 & 0 & 1 \\1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ \end{matrix}$$

 

여기서 $1$번째 원소의 상태를 보자. 현재 주어진 상태, 즉, $S_1 = 0$이라는 사실을 알 수 있다.

 

또한, $1$번째 원소는 손잡이가 돌려지는 규칙에 의해서, $1, 2, 3, 4, 5, 9, 13$번 원소가 뒤집힐 때 마다 동시에 뒤집힌다는 사실을 알 수 있다.

 

다시 말해, $X_1, X_2, X_3, X_4, X_5, X_9, X_{13}$의 값에 따라서 변하는 사실을 알 수 있다.

 

이 상황에서 $X_n$을 처음 상황에서 영행렬로 만드려고 할 때, $n$번째 원소를 돌려야 하는지의 여부라고 간주하자.

 

그러면 첫번째 원소의 처음 상황($S_1$)에서 $1, 2, 3, 4, 5, 9, 13$번 원소 중 일부 원소들이 뒤집힌다면 $0$인 상황을 만들 수 있다는 뜻이므로, 아래와 같은 식을 하나 얻어낼 수 있다.

 

$$ S_1 + X_1 + X_2 + X_3 + X_4 + X_5 + X_9 + X_{13} = 0 $$

 

여기서 $+$기호는 $GF(2)$위에서의 연산, 즉, $XOR$연산을 의미한다.

 

 

마찬가지로, 두번째 원소를 살펴보자.

 

현재 주어진 상태는 $1$이므로, $S_2 = 1$임을 알 수 있다.

 

또한, $2$번째 원소는 손잡이가 돌려지는 규칙에 의해서, $1, 2, 3, 4, 6, 10, 14$번 원소가 뒤집힐 때 마다 동시에 뒤집힌다는 사실을 알 수 있다.

 

따라서 아래의 식을 얻어낼 수 있다.

 

$$ S_2 + X_1 + X_2 + X_3 + X_4 + X_6 + X_{10} + X_{14} = 0 $$

 

 

이를 반복하면 총 $16$개의 일차 식을 얻어낼 수 있으며, 이를 가우스 소거법을 이용하면 $X_1, X_2, ... , X_{16}$까지의 값을 모두 구할 수 있다.

 

우리는 최소 값을 구하는 것이 목적이고, 당연히 손잡이를 돌려야 되는 상황이 온다면 $3$번이나 $5$번 보다는 $1$번 돌리는 것이 더 작다는 것을 알고 있으므로, $X_1$부터 $X_{16}$까지의 합을 구하면 그것이 최소 횟수라는 것을 알 수 있다.

 

 

가우스 소거법의 구현에서 중요한 것은, 가우스 소거법에서 적용되는 기본 행 연산(elementary row operation)이다.

1. 0이 아닌 상수를 행에 곱한다.
2. 두 행을 교환한다.
3. 한 행을 다른 행에 더한다.

결국 기본 행 연산을 통해 행 사다리꼴(row echelon form)을 만드는 것이 목적이다.

 

우리는 곱셈과 덧셈이 $GF(2)$위에서의 연산임을 알고 있으므로, 사실은 1번 조건이 그다지 큰 의미가 없다는 사실을 알 수 있다.

 

그러면 결국 2번과 3번만을 반복적용하여 대각부분이 1인 상삼각행렬(upper triangular matrix)를 만들면 된다.

 

 

이를 참고하여 그대로 구현하면 된다. 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 9066번 금고
# 수학, 선형대수학, 가우스 소거법
import sys
input = sys.stdin.readline

def gauss_elimination_on_GF_2(mat, A):
    n = len(mat)
    S = [0 for _ in range(n)]
    for row1 in range(n-1):
        if mat[row1][row1] == 1:
            for row2 in range(row1+1, n):
                if mat[row2][row1] == 1:
                    A[row2] ^= A[row1]
                    mat[row2] = [mat[row1][i]^mat[row2][i] for i in range(n)]
        else:
            for row2 in range(row1+1, n):
                if mat[row2][row1] == 1:
                    mat[row1], mat[row2] = mat[row2], mat[row1]
                    A[row1], A[row2] = A[row2], A[row1]
                    break
            for row2 in range(row1+1, n):
                if mat[row2][row1] == 1:
                    A[row2] ^= A[row1]
                    mat[row2] = [mat[row1][i]^mat[row2][i] for i in range(n)]
    S[-1] = A[-1]
    for row in range(n-1, -1, -1):
        k = 0
        for col in range(n-1, row, -1):
            k ^= mat[row][col]&S[col]
        S[row] = A[row]^k

    return sum(S)

def binary_mat(mat):
    n = len(mat)
    binary_matrix = [[0 for _ in range(n**2)] for _ in range(n**2)]
    A = [0 for _ in range(n**2)]
    for row in range(n):
        for col in range(n):
            if mat[row][col] == 'V':
                A[n*row+col] = 1
            for k in range(n):
                binary_matrix[n*row+col][n*row+k] = 1
            for k in range(n):
                binary_matrix[n*row+col][n*k+col] = 1
    return binary_matrix, A

T = int(input())
for _ in range(T):
    N = int(input())
    matrix = [input().rstrip().split() for _ in range(N)]
    print(gauss_elimination_on_GF_2(*binary_mat(matrix)))