링크
문제 요약
$N$ 개의 스위치와 $N$ 개의 전구가 있다. 각 스위치를 켰을 때 변화되는(=켜진 전구는 꺼지고, 꺼진 전구는 켜짐) 전구들의 번호가 주어질 때, 적절히 스위치를 눌러 단 1개의 전구만을 키는 것이 모든 번호에 대하여 가능한지 결정하는 문제이다. 즉, 1번 전구, 2번 전구, … , $N$ 번 전구만 켜지도록 만들 수 있는지 결정하면 된다.
관찰
첫번째 예시를 가지고 다음과 같은 연립 방정식을 생각해보자. 각 변수 $x_1, x_2, x_3, x_4$ 는 0 또는 1의 값을 가지고, 0은 해당 스위치가 꺼져 있음을, 1은 켜짐을 나타낸다. 또한 행렬의 원소 $A_{ij}$ 는 $i$ 번째 스위치를 이용하여 $j$ 번째 전구를 변화시킬 수 있으면 1 아니면 0의 값을 가진다. (즉, 입력으로 주어진 행렬이다.)
\[A_{11}x_1\oplus{A_{21}x_2}\oplus{A_{31}x_3}\oplus{A_{41}x_4}=1\] \[A_{12}x_1\oplus{A_{22}x_2}\oplus{A_{32}x_3}\oplus{A_{42}x_4}=0\] \[A_{13}x_1\oplus{A_{23}x_2}\oplus{A_{33}x_3}\oplus{A_{43}x_4}=0\] \[A_{14}x_1\oplus{A_{24}x_2}\oplus{A_{34}x_3}\oplus{A_{44}x_4}=0\]각 스위치가 켜졌는지 여부에 따라 $A_{ij}x_i$ 값이 0 또는 1이 되고, 이 값들을 xor 연산한 결과 값이 1인지 0인지 확인하여 현재의 스위치 조합으로는 어떤 전구가 켜져있고 꺼져있는지 쉽게 계산할 수 있음을 위 식을 통해 알 수 있다. 또한 위의 연립 방정식을 풀면, 1번 전구만 켜지고 나머지가 모두 꺼진 경우에 대한 스위치 조합을 얻게 된다. 실제로 예제에 주어진 결과물을 대입하면 결과 값이 같음을 알 수 있다.
풀이
그렇다면 이제 위의 연립 방정식을 푸는 방법을 고민하면 문제가 풀릴 것이다. 일반적인 사칙연산으로 이루어진 연립 방정식이라면 가우스 소거법을 이용하여 쉽게 해결이 가능할 것이다. 하지만 위의 식은 xor이 함께 있는 것이 문제이다. 가우스 소거법의 핵심을 생각해보면 이는 해결이 된다. 가우스 소거법은 각 열별로 pivot을 잡고, pivot이 존재하는 행을 제외한 나머지 행은 모두 해당 열 값이 0이 되도록 소거를 한다. 즉, pivot을 잡고 나머지들을 제거하는 연산을 찾으면 연립 방정식을 풀 수 있다.
본 연립 방정식을 풀 때는, 행렬의 원소값이 1 또는 0만 존재하고, 1과 1이 만나서 0으로 만드는 연산을 이용하면 가우스 소거법을 그대로 적용할 수 있다. 이는 xor 연산을 이용하면 바로 해결이 됨을 알 수 있고, 따라서 가우스 소거법을 적용하되, xor 연산을 통해 소거를 하면 된다. 이해를 돕기위해 첫번째 예제를 푸는 방법을 소개하면 아래와 같다.
\[\begin{bmatrix} 1 & 0 & 0 & 1 &\bigm| 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 &\bigm| 0 & 1 & 0 & 0\\ 1 & 0 & 1 & 0 &\bigm| 0 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 &\bigm| 0 & 0 & 0 & 1\\ \end{bmatrix}\] \[\rightarrow \begin{bmatrix} {\color{Red} 1} & 0 & 0 & 1 &\bigm| 1 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 &\bigm| 0 & 1 & 0 & 0\\ {\color{Blue} 0} & 0 & 1 & 1 &\bigm| 1 & 0 & 1 & 0\\ 0 & 1 & 1 & 0 &\bigm| 0 & 0 & 0 & 1\\ \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 0 & 0 & 1 &\bigm| 1 & 0 & 0 & 0\\ 0 & {\color{Red} 1} & 1 & 1 &\bigm| 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 1 &\bigm| 1 & 0 & 1 & 0\\ 0 & {\color{Blue} 0} & 0 & 1 &\bigm| 0 & 1 & 0 & 1\\ \end{bmatrix}\] \[\rightarrow \begin{bmatrix} 1 & 0 & 0 & 1 &\bigm| 1 & 0 & 0 & 0\\ 0 & 1 & {\color{Blue} 0} & 0 &\bigm| 1 & 1 & 1 & 0\\ 0 & 0 & {\color{Red} 1} & 1 &\bigm| 1 & 0 & 1 & 0\\ 0 & 0 & 0 & 1 &\bigm| 0 & 1 & 0 & 1\\ \end{bmatrix} \rightarrow \begin{bmatrix} 1 & 0 & 0 & {\color{Blue} 0} &\bigm| 1 & 1 & 0 & 1\\ 0 & 1 & 0 & 0 &\bigm| 1 & 1 & 1 & 0\\ 0 & 0 & 1 & {\color{Blue} 0} &\bigm| 1 & 1 & 1 & 1\\ 0 & 0 & 0 & {\color{Red} 1} &\bigm| 0 & 1 & 0 & 1\\ \end{bmatrix}\]빨간색은 pivot, 파란색은 pivot으로 인해 지워지는 열의 원소를 표기했다. 자명히 오른쪽 augmented matrix 에서 각 $i$ 번째 열을 확인함으로써 $i$ 번째 전구만을 켜는데 필요한 스위치들의 번호를 얻을 수 있다. 또한 왼쪽 행렬이 identity matrix가 나오지 않으면 해는 존재하지 않는다. 가우스 소거법의 시간 복잡도는 $O(N^3)$ 이고 bitset 등을 이용하여 상수를 줄이는 방법도 존재한다.