저는 게임을 좋아합니다. 특히 좋아하는 장르는 롤플레잉 게임이나 퍼즐 게임인데요. 롤플레잉 게임을 할 때는 주로 그 속에 담긴 이야기를 따라가는 것을 즐기고 퍼즐 게임을 할 때는 복잡한 문제를 시간을 들여 해결할 때 큰 희열을 느낍니다. 만약 롤플레잉 게임에 흥미로운 퍼즐 요소가 섞여 있거나 퍼즐 게임에 감동적인 이야기가 더해져 있다면 말하지 않아도 제 취향일 것입니다.
글을 쓰는 현재로부터 약 두세 달 전 제 취향의 게임을 하나 플레이했습니다. 바로 「투 더 문(To the Moon)」입니다. 사실 이 게임을 처음 구매할 때는 이 게임에 퍼즐 요소가 들어있을 줄 몰랐습니다. 스팀에서 게임을 구매하는 분들이라면 많이 공감하실텐데, 저는 스팀에서 할인 행사를 진행할 때 게임을 좀 쟁여 놓는 편입니다. 이 게임도 할인 행사 중에 얼핏 스토리가 그렇게 좋다는 말을 들은 기억이 있어서 사 둔 게임이었습니다. 그렇게 몇 달을 묵혀 두다가 한번 플레이를 해 봤는데, 웬걸 게임에 퍼즐이 있었습니다.
대개 퍼즐 게임들이 그렇듯이 「투 더 문」의 퍼즐도 처음에는 그렇게 어렵지 않았지만, 나중에는 좀 복잡해지더군요. 그렇게 어려운 퍼즐들에서 한참 고민을 하던 차에 퍼즐을 해결하는 간단한 전략이 제 머릿속을 스치고 지나갔습니다. 그 이후로 게임이 끝날 때까지 퍼즐은 손쉽게 해결할 수 있었습니다.
엔딩을 본 다음 저는 컴퓨터과학을 전공한 사람답게 문득 「투 더 문」 퍼즐을 푸는 알고리즘이 없을까 생각을 했습니다. 왜냐하면 제가 퍼즐을 풀 때의 전략이 (완벽하지는 않지만) 알고리즘적으로 구성될 수 있을 것 같았거든요. 이후 이 생각에 대해 연구실 동료들과도 이야기를 나누어 보고, 저 스스로도 틈틈이 생각을 해 봤습니다. 그리고 최근에 드디어 퍼즐을 푸는 알고리즘을 만드는 데 성공하였습니다. 이번 포스트에서는 이를 만들기 위해서 그동안 고찰했던 내용들을 담았습니다.
※ 주의! 본문에는 「투 더 문」 게임 플레이에 관한 스포일러가 포함되어 있으니 유의하시기 바랍니다.
퍼즐 소개
게임의 퍼즐은 다음과 같습니다. 먼저 우리에게는 직사각형 모양의 격자가 주어집니다. 이 격자의 몇몇 칸은 흐린 상태입니다. 또한 우리에게는 오브(orb)라는 일종의 장치가 주어지는데, 이는 격자의 각 행(가로줄)의 왼쪽과 각 열(세로줄)의 아래, 그리고 좌측 하단 구석에 하나씩 위치하고 있습니다.
오브는 칸의 상태에 영향을 주며 각 오브마다 작동하는 방식이 조금씩 다릅니다.
- 행 오브(각 행의 왼쪽에 딸린 오브)는 해당 행의 모든 칸의 상태를 반대로 뒤집는다. 즉, 원래 흐린 칸이었으면 맑은 칸으로 바꾸고, 원래 맑은 칸이었으면 흐린 칸으로 바꾼다.
- 열 오브(각 열의 아래쪽에 위치한 오브)는 해당 열의 모든 칸의 상태를 반대로 뒤집는다.
- 대각선 오브(좌측 하단에 위치한 오브)는 격자의 가장 왼쪽 아래 구석에서부터 우측 상단 방향의 모든 칸의 상태를 반대로 뒤집는다.
우리의 목표는 오브를 사용해 모든 칸을 맑게 만드는 것입니다. 대신 오브를 사용하는 총 횟수에 제한이 있습니다.
서문에서 말씀 드린 제 머릿속을 스치고 간 전략은 다음과 같습니다. 만약 처음 주어진 상태에서 바로 푸는 게 어렵다면 대각선 오브를 한 번 누르는 것입니다. 그러면 항상 풀기 쉬운 꼴로 바뀌게 되더군요. 예를 들어 그림 1의 예시는 바로 풀기 어려워 보입니다. 따라서 대각선 오브를 한 번 동작시키면 그림 3-(3)과 같은 모양이 됩니다. 여기서는 행 오브 a, 행 오브 b, 열 오브 ii, 열 오브 iv를 누르면 모든 칸을 맑게 만들 수 있습니다.
직관적으로는 위 전략이 잘 들어맞을 것 같고, 실제로도 잘 됩니다. 그렇다면 어째서 잘 되는 것일까요? 이론을 좋아하는 컴퓨터과학도로서 이 질문에 대한 답을 찾고 싶었습니다. 이를 위해 고찰한 내용들을 아래에 시간 순으로 적었습니다.
고찰 1. 횟수 제한이 없을 때 정답이라도 구할 수는 있는가?
「투 더 문」의 엔딩을 본 다음 날, 저는 연구실 동료들에게 이 퍼즐을 공유해 주었습니다. 이에 관해 함께 토의를 나누었고, 결과적으로 오브를 쓰는 횟수에 제한이 없을 때 모든 칸을 맑게 만드는 알고리즘을 만들 수 있었습니다. 결론부터 말씀을 드리면 2-SAT 문제로 환산(reduce)하는 것입니다.
이 알고리즘을 소개하기에 앞서 몇 가지 유용한 성질들을 알아보겠습니다. 첫 번째 성질은 퍼즐에서 각 오브를 몇 번씩 눌렀는지만 중요할 뿐, 오브들을 어떤 순서대로 눌렀는지는 상관이 없다는 것입니다.
정리 1. 오브를 누르는 순서
퍼즐에서 오브를 작동시키는 서로 다른 두 전략을 생각하자. 모든 오브에 대해, 만약 이를 누르는 총 횟수가 두 전략에서 같다면, 최종적으로 격자의 모든 칸은 각각 동일한 상태를 갖는다. 즉, 한 전략이 끝났을 때 어떤 칸이 흐리면 다른 전략이 끝났을 때도 이 칸은 흐리며, 맑다면 똑같이 맑다.
[증명] 격자의 각 칸을 생각해 봤을 때, 이 칸의 상태가 뒤집히려면, 이 칸에 영향을 주는 오브들이 작동되는 횟수의 합이 홀수이면 됩니다. 반대로 상태가 그대로 유지되려면, 그 합이 짝수이면 됩니다. 이는 어떤 순서로 하든 상관이 없습니다. 따라서 각 오브를 누르는 총 횟수가 동일한 두 전략은 똑같은 상태의 격자를 도출합니다. ■
다음 성질은 퍼즐에서 오브를 두 번 이상 누르면 멍청하다는 것을 알려 줍니다.
정리 2. 오브를 누르는 횟수
퍼즐에서 어떤 전략이 주어졌을 때, 그 전략과 동일한 상태의 격자를 도출하면서 각 오브는 최대 한 번씩만 누르는 전략이 존재한다.
[증명] 정리 1에서 오브를 누르는 순서는 중요하지 않다고 하였으므로 각 오브를 순서대로 주어진 전략에서 누르는 총 횟수만큼 작동시키고 다음 오브로 넘어가는 전략도 주어진 전략과 동일한 결과를 도출합니다. 이렇게 만든 전략에서 한 오브를 여러 번 누르는 때를 생각해 봅시다. 이때 오브를 두 번 누르면 다시 원상태로 돌아온다는 것을 알 수 있습니다. 따라서 만들어진 전략에서 홀수 번 누르는 오브만 한 번씩 누르는 전략은 만들어진 전략과, 나아가 원래 주어진 전략과 똑같은 상태의 격자를 반환하게 됩니다. ■
따라서 우리는 일반성을 잃지 않고 순서에 상관 없이 각 오브를 누를지 말지만 결정하는 것으로 퍼즐을 해결하는 전략을 구상할 수 있습니다. 이제 어떤 오브를 작동시켜야 하는지 알아 봅시다. 먼저 대각선 오브를 사용하지 않는 전략에 대해서만 생각해 보겠습니다. 그 다음 대각선 오브를 사용할 수 있는 일반적인 경우로 논의를 확장하겠습니다.
\(i\) 번째 행의 오브를 눌렀는지 여부를 나타내는 논리 변수를 \(x_i\), \(j\) 번째 열의 오브의 작동 여부를 나타내는 논리 변수를 \(y_j\)라고 하죠. 만약 \(i\) 번째 행과 \(j\) 번째 열의 교차점인 \( (i, j) \)가 흐린 상태라면 이를 맑은 상태로 돌려 놓기 위해서는 \(i\) 번째 행의 오브나 \(j\) 번째 열의 오브 중 정확히 하나만을 눌러주어야 합니다. 다시 말해, \[ ( x_i \wedge \neg y_j ) \vee (\neg x_i \wedge y_j) \tag{1} \] 가 참이어야 \( (i, j) \)가 맑은 상태로 바뀌게 됩니다.
같은 이치로 이번에는 \( (i, j) \)가 맑은 상태였다고 합시다. 오브를 모두 누른 다음에 여전히 이 칸이 맑은 상태를 유지하기 위해서는 해당하는 행과 열의 오브를 둘 다 누르든지, 둘 다 누르지 말아야 합니다. 즉, \[ (x_i \wedge y_j) \vee (\neg x_i \wedge \neg y_j) \tag{2} \]가 참이어야 \( (i, j) \)가 맑은 상태로 유지가 됩니다.
따라서 퍼즐의 입력에서 맑은 칸의 집합을 \( A \), 흐린 칸의 집합을 \( B \)라고 했을 때, \[ \bigwedge_{(i, j) \in A} \left[ (x_i \wedge \neg y_j) \vee (\neg x_i \wedge y_j) \right] \wedge \bigwedge_{(i, j) \in B} \left[ (x_i \wedge y_j) \vee (\neg x_i \wedge \neg y_j) \right] \tag{3} \]를 참이 되도록 하는 \( x_i \), \( y_j \)를 구한 다음 이에 따라서 오브를 눌러주면 퍼즐을 풀 수 있습니다.
위 논리식을 약간 손 보면 우리가 익숙한 모양으로 바꿀 수 있습니다. 먼저 식 1을 정리하면, \[ \begin{array} {rl} (x_i \wedge \neg y_j) \vee (\neg x_i \wedge y_j) & = [(x_i \wedge \neg y_j) \vee \neg x_i] \wedge [(x_i \wedge \neg y_j) \vee y_j] \\ & = [(x_i \vee \neg x_i) \wedge (\neg y_j \vee \neg x_i)] \wedge [ (x_i \vee y_j) \wedge (\neg y_j \vee y_j) ] \\ & = (\neg y_j \vee \neg x_i) \wedge (x_i \vee y_j) \end{array} \tag{4} \]이 됩니다. 여기서 첫 번째와 두 번째 등식은 분배 법칙을 통해 얻은 것이고, 마지막 등식은 \( x_i \vee \neg x_i \)와 \( y_j \vee \neg y_j \)가 항상 참이라는 사실에서 이끌어 냈습니다. 위와 같은 방식으로 식 2를 정리하면, \[ (x_i \wedge y_j) \vee (\neg x_i \wedge \neg y_j) = (x_i \vee \neg y_j) \wedge (y_j \vee \neg x_i) \tag{5} \]를 얻을 수 있습니다.
식 4와 5를 식 3에 대입하면 \[ \bigwedge_{(i, j) \in A} \left[ (x_i \vee y_j) \wedge (\neg x_i \vee \neg y_j) \right] \wedge \bigwedge_{(i, j) \in B} \left[ (x_i \vee \neg y_j) \wedge (\neg x_i \vee y_j) \right] \tag{6} \]를 얻을 수 있습니다. 이는 AND-of-OR 꼴이고 각 OR 절(clause)에는 정확히 두 개의 리터럴(literal)로 이루어져 있으므로 2-SAT 문제의 입력입니다. 2-SAT 문제는 다항 시간에 해결이 가능합니다. (2-SAT을 푸는 방법은 나중에 포스팅해 보도록 하겠습니다.)
이로써 대각선 오브를 사용하지 않는 경우에 퍼즐을 푸는 방법을 구하였습니다. 정확히는 만약 퍼즐을 풀 수 있다면 한 번씩 눌러 줘야하는 오브가 무엇인지를 알려 주고, 풀 수 없다면 풀 수 없다고 알려주는 방법을 구하였습니다. 그러면 대각선 오브도 같이 사용할 수 있는 경우에는 어떻게 될까요?
쉽게 생각할 수 있는 방법은 대각선 오브에 해당하는 논리 변수를 두어 위 식에 포함시키는 것입니다. 굳이 어떻게 하면 되는지 보여드리지는 않겠습니다만, 그다지 어렵지 않게 확장할 수 있다는 것은 알 수 있을 것입니다. 문제는 그렇게 되면 리터럴이 세 개 이상인 절이 나오게 된다는 것입니다. 3-SAT 문제는 잘 알려진 NP-완전(NP-complete) 문제이며, 따라서 3-SAT 문제를 다항 시간에 해결하는 것은 기대하기 어렵습니다.
이를 회피하기 위해서 대각선 오브의 개수에 집중하시기 바랍니다. 이 오브는 퍼즐에서 정확히 하나 밖에 없습니다. 게다가 앞에서 보인 정리 1과 2를 통해, 대각선 오브를 처음에 한 번 누르는 경우와 그렇지 않은 경우 두 개만 고려해 주면 충분하다는 사실을 추론할 수 있습니다. 만약 누른 경우에는 대각선 위의 칸의 상태를 뒤집어 준 다음, 이 상태에 대해서 위의 2-SAT 문제 입력을 만들어 주면 되겠습니다.
이를 정리하면 다음과 같은 퍼즐을 푸는 알고리즘을 고안할 수 있습니다.
알고리즘 1. 2-SAT을 활용한 풀이 (횟수 제한 없음)
입력: 격자의 상태
출력: 모든 칸이 맑아지도록 눌러야 하는 오브들 (혹은 그러한 방법이 존재하지 않음을 알림)
- 대각선 오브를 누른 경우와 누르지 않은 경우 각각에 대해 아래를 수행한다.
- 각 칸의 상태에 맞게 식 6을 구성한다.
- 2-SAT 알고리즘을 사용하여 식 6을 해결한다.
- 만약 두 경우 중 한 경우에라도 식 6이 참이 되는 논리 변수의 할당이 존재하면, 그에 따라 참 값을 갖는 오브들을 반환한다. 둘 다 참이 되지 못한다면 그러한 방법이 존재하지 않는다고 알린다.
고찰 2. 횟수 제한이 있을 때도 정답을 구할 수 있는가?
이전 절에서는 퍼즐을 2-SAT 문제로 환산하여 해결하는 방법을 알아 보았습니다. 이를 통해, 퍼즐이 해결 가능한 경우, 어떤 오브를 눌러야 하는지에 대해서는 구할 수 있었습니다. 하지만 퍼즐에는 조건이 한 가지 더 있었습니다. 바로 오브를 누르는 횟수에 제약이 있었습니다. 안타깝게도 알고리즘 1을 통해서는 횟수 제약까지는 맞춰 주는 것이 쉽지 않아 보입니다.
이를 해결하기 위해서는 2-SAT과 같은 다른 문제로 환산하기 보다 퍼즐 그 자체에 집중을 하는 것이 좋겠다고 생각했습니다. 환산이라 함은 결국 "더 어려운" 문제의 입력으로 바꾸어서 답을 구하는 과정이므로, 분명 "더 쉬운" 원래 문제만이 갖는 특징이 있을 것으로 생각했기 때문입니다. 며칠 틈틈이 생각한 결과, 아래의 흥미로운 결론을 얻을 수 있었습니다.
앞에서 우리는 일반성을 잃지 않고 퍼즐을 푸는 전략이 순서 상관 없이 어떤 오브를 누를지만 정해주면 된다는 것을 배웠습니다. 또한, 대각선 오브에 대해서는, 이를 눌렀을 때와 누르지 않았을 때로 나누어서 각각 생각해 줘도 괜찮다는 것도 알았죠.
따라서 행의 집합을 \(R\), 열의 집합을 \(C\)라고 했을 때, 전략은 \( R \cup C \)의 부분집합으로 표현할 수 있습니다. 여기서 전략의 의미는 행 오브 몇 개와 열 오브 몇 개를 누르는 행동 자체를 의미하며, 따라서 전략을 수행했을 때 결과적으로 모든 칸이 맑아져야 할 필요는 없습니다. 만약 그렇게 된다면 그 전략이 우리의 최종 정답이 되는 것이죠. 행과 열을 구분하기 위해 \( X \subseteq R \), \( Y \subseteq C \)에 대해 \(X\)의 행 오브와 \(Y\)의 열 오브를 누르는 전략을 \( (X, Y) \)로 표현하겠습니다.
첫 번째 흥미로운 결과는 \( (X, Y) \) 대신 각각의 여집합인 \( (R \setminus X, C \setminus Y) \)를 취해도 동일한 결과를 얻는다는 점입니다.
정리 3. 같은 결과를 얻을 충분 조건
어떤 전략 \( (X, Y) \)에 대해, 이 전략을 수행했을 때의 격자의 상태는 \( (X', Y') :=(R \setminus X, C \setminus Y) \)를 수행했을 때의 격자의 상태와 동일하다.
[증명] 만약 \( i \in X, j \in Y \)라면, \( i \not\in X', j \not\in Y' \)이 되어 칸 \( (i, j) \)는 두 전략에서 모두 현재 상태를 유지합니다. 만약 \( i \in X, j \not\in Y \)라면, \( i \not\in X', j \in Y' \)이 되므로 칸 \( (i, j) \)는 두 전략에서 모두 상태가 뒤집힙니다. 같은 원리로 \( i \not\in X, j \in Y \)와 \( i \not\in X, j \not\in Y \)의 경우에는 두 전략에서 각각 상태가 뒤집히고, 상태가 유지된다는 것을 알 수 있습니다. 임의의 \(i, j\)와 모든 경우에 대해서 보였으므로 두 전략은 동일한 상태의 격자를 반환합니다. ■
다음 결과는 놀랍게도 정리 3의 역도 성립한다는 것입니다. 참고로 \( (X', Y') \neq (X, Y) \)라고 해서 \( X' \neq X \)라는 뜻은 아닙니다. \( Y' \neq Y \)라면 \( X' = X \)일 수도 있습니다.
정리 4. 같은 결과를 얻을 필요 조건
어떤 두 전략 \( (X, Y), (X', Y') \)에 대해, \( (X', Y') \neq (X, Y) \)이고 \( (X', Y') \neq (R \setminus X, R \setminus Y) \)일 때, 두 전략을 수행한 후의 격자 상태는 다르다.
[증명] 첫 번째로 \(X'\)이 \(X\)나 \(R \setminus X\)가 아닌 경우를 따져 보겠습니다. 그러면 분명히 \(X\)에만 속하거나 \(X'\)에만 속한 행 \(i_1\)과 둘 다에 속하거나 둘 다에 속하지 않는 행 \(i_2\)가 존재합니다. 다시 말해, \[ i_1 \in (X \setminus X') \cup (X' \setminus X) \text{, } i_2 \in (X \cap X') \cup (A \setminus (X \cup X')) \]를 만족합니다.
이중에서 \( i_1 \in (X \setminus X') \)과 \( i_2 \in (X \cap X') \)의 경우에 대해서만 증명을 보이겠습니다. 나머지 경우는 비슷한 방식으로 어렵지 않게 보일 수 있습니다. 행 \( i_1 \)은 \(X\)에만 있고 \( X' \)에는 없기 때문에 임의의 열 \(j\)에 대해 칸 \( (i, j) \)가 두 전략을 모두 수행한 다음 같은 상태가 되려면 \(Y'\)은 \(Y\)와 반대로 동작해야 합니다. 즉, \( j \in Y \)라면 \( j \not\in Y' \)이고 \( j \not\in Y \)라면 \( j \in Y' \)이어야 합니다. 반면, 행 \(i_2\)는 \(X\)와 \(X'\)에 모두 속해있으므로 임의의 열 \(j\)에 대해 같은 상태를 갖기 위해서는 \( Y \)와 \(Y'\)이 동일해야 합니다. 다시 말해, \( j \in Y \)라면 \( j \in Y' \)이고, \( j \not\in Y \)라면 \( j \not\in Y' \)이죠. 이는 행 \( i_1 \)에서 얻은 식에 모순입니다.
\( Y' \)이 \(Y\)나 \( C \setminus Y \)가 아닌 경우는 위 경우와 증명이 흡사하므로 생략합니다. 따라서 남은 경우는 \( X' \)이 \( X \)나 \( R \setminus X \)이고 \( Y' \)이 \( Y \)나 \( C \setminus Y \)인 경우입니다. 정리의 조건에 의해 \( (X', Y') = (X, C \setminus Y) \)나 \( (X', Y') = (R \setminus X, Y) \)만 고려해 주면 됩니다. 두 경우 모두 증명은 흡사하므로 앞의 경우에 대해서만 보이겠습니다. 임의의 행 \(i\)는 \(X\)와 \(X'\)에 동시에 속하든지 속하지 않을 것입니다. 하지만 임의의 열 \(j\)는 \( Y \)에만 속하든지 \( Y' \)에만 속할 것입니다. 따라서 칸 \( (i, j) \)는 정확히 반대의 상태를 갖게 됩니다. ■
정리 3과 정리 4를 통해서 우리는 서로 다른 두 전략이 동일한 결과를 출력하기 위한 필요충분 조건은 두 전략이 서로 여집합의 관계에 있다는 것을 알 수 있습니다. 따라서 원래 주어진 퍼즐이 해결 가능하다면, 모든 칸을 맑게 만드는 전략은 정확히 두 가지 존재한다는 것을 알 수 있습니다. 그중 크기가 작은 전략이 곧 우리가 찾고자 하는 것이 되겠죠.
이제 문제는 원래 주어진 퍼즐이 해결 가능한지를 판단해 내는 것입니다. 다음 정리는 퍼즐이 해결 가능하려면 최소한으로 갖추어야 하는 필요 조건을 나타냅니다.
정리 5. 퍼즐이 해결 가능할 필요 조건
\( |R| \geq 2, |C| \geq 2 \)인 어떤 퍼즐에 다음을 만족하는 서로 다른 두 행 \( i, i' \in R\)과 서로 다른 두 열 \( j, j' \in C \)가 존재한다면 이 퍼즐은 풀 수 없다.
- \( (i, j) \)와 \( (i', j) \)의 상태가 서로 같으면서 \( (i, j') \)과 \( (i', j') \)의 상태는 서로 다르다.
[증명] \((i, j')\)과 \( (i', j') \)의 상태가 서로 다르므로 둘 중 하나는 분명 흐린 상태입니다. 일반성을 잃지 않고 \( (i, j') \)이 흐린 칸이고 \( (i', j') \)은 맑은 칸이라 하겠습니다. \( (i, j') \)이 흐린 칸이므로 분명 행 \(i\)의 오브와 열 \(j'\)의 오브 중 정확히 하나만 누를 수 있습니다. 먼저 행 \(i\)의 오브만 눌렀다고 가정해 봅시다. 여기서 또 다음 두 경우로 나뉘게 됩니다.
- \( (i, j) \)와 \( (i', j) \)가 둘 다 맑은 경우. 이 경우에는 \( (i, j) \)가 흐려지게 되고, 따라서 열 \(j\)의 오브를 눌러야 합니다. 이번에는 \( (i', j) \)가 흐려지게 될 것이고 이를 해소하기 위해 행 \(i'\)의 오브를 눌러야 합니다. 그러면 \( (i', j') \)이 흐린 칸이 됩니다. 이를 맑은 칸으로 만드려면 \(j'\)을 눌러야 하므로, 이는 모순이 됩니다.
- \( (i, j) \)와 \( (i', j) \)가 둘 다 흐린 경우. 이 경우에는 \( (i, j) \)가 맑아지므로, 열 \(j\)의 오브를 누르면 안 됩니다. 여전히 \( (i', j) \)는 흐리므로 행 \(i'\)의 오브를 눌러야 합니다. 하지만 그러면 \( (i', j') \)이 흐린 칸이 되며 앞의 경우와 마찬가지로 모순이 됩니다.
열 \(j'\)의 오브만 누른 경우도 위와 비슷하게 \( (i, j) \)과 \( (i', j) \)의 상태에 맞추어 분석하면 쉽게 모순을 이끌어낼 수 있습니다. ■
정리 5가 퍼즐이 해결 가능할 필요 조건인 이유는 그 대우를 생각하면 됩니다. 정리 5의 대우 명제는 다음과 같습니다.
어떤 퍼즐이 행 오브와 열 오브만을 가지고 풀 수 있으려면, \( |R| = 1 \)이거나 \( |C| = 1 \)이거나 아니면 서로 다른 두 행\( i, i' \)과 서로 다른 두 열 \( j, j' \)에 대해 \( (i, j) \)와 \( (i', j) \)의 상태가 같다면 \( (i, j') \)과 \( (i', j') \)의 상태가 같고, 다르다면 다르다.
\( |R| \geq 2, |C| \geq 2 \)에서 이를 만족하는지 판별하는 방법은 어렵지 않습니다. 첫 번째 행을 기준으로 다른 모든 행의 상태가 첫 번째 행과 동일하거나 정확히 반대인지를 검증하면 됩니다. 그러면 임의의 두 행 \( i, i' \)과 두 열 \( j, j' \)에 대해 \( (i, j) \)와 \( (i', j) \)가 서로 같은 상태라면 \( (i, j') \)과 \( (i', j') \)도 같은 상태이고, 다른 상태라면 다른 상태일 것입니다.
추가적으로 정리 5를 통해서 우리는 대각선 오브를 작동시킬지 말지를 결정할 수 있습니다.
정리 6. 대각선 오브의 작동 여부
\( |R| \geq 2, |C| \geq 2, |R| + |C| \geq 5 \)인 퍼즐에서, 만약 대각선 오브를 작동시키지 않았을 때 행 오브와 열 오브만을 가지고 모든 칸을 맑은 상태로 만들 수 있다면, 대각선 오브를 작동시킨 후에는 불가능하다.
[증명] 조건에 의해 행의 개수나 열의 개수 중 하나는 3보다 크거나 같습니다. 일반성을 잃지 않고 \( |R| \geq 2, |C| \geq 3 \)이라고 하겠습니다. 또한 쉽게 표현하기 위해 격자의 가장 아래 행을 첫 번째 행, 그 위의 행을 두 번째 행이라고 하겠습니다. 대각선 오브를 누르기 전에 행 오브와 열 오브만을 통해 모든 칸을 맑은 상태로 만들 수 있다고 하였으므로, 정리 5에 의해 \( (1, 1) \)과 \( (2, 1) \)이 같은 상태, \( (1, 3) \)과 \( (2, 3) \)이 같은 상태이거나 각각이 다른 상태여야 합니다. 두 경우의 증명은 비슷하므로 두 쌍이 각각 같은 상태였을 때만 보이도록 하겠습니다. 이 상태에서 대각선 오브를 작동시키면 정확히 \( (1, 1) \)의 상태만 뒤바뀌게 됩니다. 그러면 \( (1, 1) \)과 \( (2, 1) \)의 상태는 서로 다르지만 \( (1, 3) \)과 \( (2, 3) \)은 서로 같아지게 됩니다. 따라서 정리 5에 의해 이 상태의 격자에서는 행 오브와 열 오브만 가지고 모든 칸을 맑게 만들 수 없습니다. ■
이 정리가 알려 주는 사실은 처음에 주어진 퍼즐이 만약 행 오브와 열 오브만 가지고 풀 수 있었다면 대각선 오브를 동작시킨 후에는 절대 풀 수 없으니 더 적은 횟수의 전략이 존재하는지를 따질 필요가 없다는 것입니다.
정리 6이 다루지 않은 경우는 \( |R| = 1 \)일 때와 \( |C| = 1 \)일 때, 그리고 \( |R| = |C| = 2 \)일 때입니다. 여기서 \( |R| = 1 \)일 때나 \( |C| = 1 \)일 때는 대각선 오브가 각각 첫 번째 열 오브와 (아래에서) 첫 번째 행 오브와 동일하게 동작하므로 굳이 대각선 오브를 누를 필요가 없습니다. \( |R| = |C| = 2 \)인 퍼즐은 크기가 그리 크지 않으므로 그냥 따로 모든 경우를 다 탐색하여 해결하면 되겠습니다.
여기까지 밝혀낸 사실을 토대로 우리는 알고리즘 1을 아래와 같이 수정할 수 있습니다. 이는 횟수 제한도 만족하는 전략을 찾아 주는 알고리즘입니다.
알고리즘 2. 2-SAT을 활용한 풀이 (횟수 제한도 고려함)
입력: 격자의 상태, 횟수 제한 \(k\)
출력: 모든 칸이 맑아지도록 눌러야 하는 오브들 (혹은 그러한 방법이 존재하지 않음을 알림)
- \(|R| = |C| = 2\)인 경우는 따로 계산한다.
- 정리 5에 의거해 현재 퍼즐을 행 오브와 열 오브만 가지고 풀 수 있는지 판단한다. 불가능하면 대각선 오브를 누른다. 여전히 정리 5에 의거해 불가능하면 그러한 방법이 존재하지 않는다고 알린다.
- 각 칸의 상태에 맞게 식 6을 구성하고 2-SAT 알고리즘을 사용하여 이를 해결한다.
- 식 6이 참이 되는 논리 변수의 할당이 존재하지 않으면 그러한 방법이 존재하지 않는다고 알린다.
- \(X\)를 식 6에서 참인 행 오브의 집합, \( Y \)를 식 6에서 참인 열 오브의 집합이라고 하자.
- 만약 \( |X| + |Y| > |R \setminus X| + |C \setminus Y| \)이면, \( X := R \setminus X, Y := C \setminus Y \)
- \( (X, Y) \)를 반환한다. (대각선 오브를 누른 경우에는 같이 반환한다.) 만약 이 크기가 \(k\)를 넘으면 그러한 방법은 존재하지 않는다고 알린다.
고찰 3. 정말로 2-SAT이 필요한가?
드디어 2-SAT을 활용하여 「투 더 문」 퍼즐을 해결하는 알고리즘을 구현하였습니다. 여기까지 온 저는 다음 질문들을 머릿속으로 되내었습니다.
- 정말로 2-SAT이 필요한가?
- 정리 5가 사실은 필요충분 조건이지 않은가?
이 질문들을 생각한 이유는 게임을 하면서 얻은 경험 때문입니다. 정리 5의 대우 명제를 만족하는 모양의 퍼즐은 항상 풀렸고, 또 그 방법을 찾는 것도 그리 어렵지 않았기 때문입니다. 다시금 며칠 틈틈이 생각을 해 보니 다음과 같은 훨씬 간단한 알고리즘을 생각할 수 있었습니다.
알고리즘 3. 간단한 알고리즘
입력: 격자의 상태, 횟수 제한 \(k\)
출력: 모든 칸이 맑아지도록 눌러야 하는 오브들 (혹은 그러한 방법이 존재하지 않음을 알림)
- \(|R| = |C| = 2\)인 경우는 따로 계산한다.
- 정리 5에 의거해 현재 퍼즐을 행 오브와 열 오브만 가지고 풀 수 있는지 판단한다. 불가능하면 대각선 오브를 누른다. 여전히 정리 5에 의거해 불가능하면 그러한 방법이 존재하지 않는다고 알린다.
- 첫 번째 행에서 맑은 칸을 갖는 열의 집합을 \(Y_1\), 흐린 칸을 갖는 열의 집합을 \(Y_2\)라고 하자.
- \( Y_2 \)의 열 오브를 모두 눌렀다고 가정했을 때 맑은 칸으로만 이루어진 행의 집합을 \(X_1\), 흐린 칸으로만 이루어진 행의 집합을 \(X_2\)라고 하자.
- \( |X_1| + |Y_1| \)과 \( |X_2| + |Y_2| \) 중 크기가 더 작은 것을 \( (X, Y) \)라 하자.
- \( (X, Y) \)를 반환한다. (대각선 오브를 누른 경우에는 같이 반환한다.) 만약 이 크기가 \(k\)를 넘으면 그러한 방법이 존재하지 않는다고 알린다.
이 알고리즘이 올바르게 동작함을 보이도록 하겠습니다. 첫 번째는 \( X_1, X_2 \)가 \(R\)을 분할(partition)한다는 것입니다.
정리 7. \( X_1, X_2 \)의 분할 성질
알고리즘 3에서 \(X_1\) 과 \(X_2\)는 \(R\)을 분할한다. 즉, \(Y_2\)의 오브를 모두 눌렀을 때, 격자에는 맑은 칸으로만 이루어진 행과 흐린 칸으로 이루어진 행만 존재한다.
[증명] 정리 5에 의해 단계 3을 수행할 시점에는 \( |R| = 1 \)이거나 \( |C| = 1\)이거나 서로 다른 두 행 \( i, i' \)과 두 열 \( j, j' \)에 대해 \( (i, j) \)와 \( (i', j) \)의 상태가 같다면 \( (i', j) \)과 \( (i', j') \)의 상태가 같고, 다르다면 다릅니다.
처음 두 경우는 쉽습니다. \( |R| = 1 \)이라는 뜻은 행이 하나뿐이라는 것이고, 따라서 흐린 칸의 오브를 모두 누르면 이 행은 모두 맑아지게 됩니다. 반면 \( |C| = 1 \)이면 모든 행이 각각 하나의 칸으로만 이루어져 있다는 뜻이므로 명제가 자명하게 성립합니다.
이제 마지막 복잡한 경우를 생각해 보겠습니다. 첫 번째 행에서 임의의 두 칸 \( (1, j) \)와 \( (1, j') \)을 갖고 오겠습니다. 만약 두 칸의 상태가 \(Y_2\)의 오브를 누르기 전에 동일하다면 임의의 다른 행 \(i'\)에 대해서 \( (i', j) \)와 \( (i', j') \)의 상태도 가정에 의해서 같다는 것을 알 수 있습니다. 이때 \( j \)와 \(j'\)은 동시에 \(Y_2\)에 들어 있든지 들어 있지 않으므로 \( Y_2 \) 오브를 누른 후에도 \( (i', j) \)와 \( (i', j') \)의 상태는 동일합니다.
이번에는 \( (1, j) \)와 \( (1, j') \)의 상태가 달랐다고 합시다. 그러면 가정에 의해 \( (i', j) \)와 \( (i', j') \)의 상태도 다릅니다. 이 경우에는 \(j\) 혹은 \(j'\) 중 정확히 하나의 열만 \(Y_2\)에 들어가므로 \( Y_2 \)의 오브를 누른 다음에는 \( (i', j) \)와 \( (i', j') \)의 상태가 동일해집니다.
\(Y_2\)의 오브를 누른 후에 첫 번째 행이 모두 맑은 상태의 칸으로 이루어진다는 것은 어렵지 않게 보일 수 있고, 앞에서 다른 임의의 행 \(i'\)에 대해 임의의 두 칸 \( (i', j) \)와 \( (i', j') \)이 같은 상태를 가진다는 것을 보였으므로 명제가 성립합니다. ■
정리 7에 의해 \( (X_2, Y_2) \)가 모든 칸을 맑게 만드는 전략임을 알 수 있습니다. 또한 정리 7에 의해 \( X_1 = R \setminus X_2 \)라는 것을 알 수 있으며 \( Y_1 = C \setminus Y_2 \)는 정의에서 바로 알 수 있습니다. 따라서 정리 3에 의해 \( (X_1, Y_1) \)도 모든 칸을 맑게 만드는 전략이며, 정리 4에 의해 이 두 전략만이 단계 2가 끝난 후의 퍼즐을 해결할 수 있다는 것도 이끌어낼 수 있습니다. 이것으로 알고리즘 3이 올바르게 동작한다는 증명이 완성됩니다.
이 알고리즘을 통해 이번 절을 시작할 때 제시한 질문들에 대한 답을 줄 수 있습니다. 이 알고리즘은 2-SAT으로 환산할 필요 없이 간단히 칸을 비교하는 것만으로 동작합니다. 또한 \( |R| = 1 \)이거나 \(|C| = 1\)이거나 임의의 두 행 \(i, i'\)과 두 열 \(j, j'\)에 대해 \( (i, j) \)와 \( (i, j') \)의 상태가 같을 때 \( (i', j) \)와 \( (i', j') \)의 상태가 같고, 다를 때는 다르기만 한 퍼즐에 대해서 이를 해결하는 알고리즘을 제시하였으므로 정리 5가 사실은 필요충분 조건이라는 것도 알 수 있습니다.
마치며
이것으로 「투 더 문」에 나오는 퍼즐을 푸는 알고리즘에 대해 고민했던 내용들에 대한 정리를 모두 마칩니다. 게임을 시작할 때는 제가 게임에 관해 블로그 포스팅을 할 줄 몰랐는데, 막상 이렇게 글을 적고 나니 재미있군요. 물론 예상보다 글이 길어져서 쓰는데 어려움이 있었던 것도 사실이지만, 다 끝내고 나니 후련합니다. 다음에도 다른 게임과 관련하여 흥미로운 주제로 포스팅을 할 기회가 있으면 좋겠습니다.
읽어 주셔서 고맙습니다. :)
'연습 노트' 카테고리의 다른 글
| 형독 카트라이더 디비디비딥 최적(?)의 위치 선정 (0) | 2022.08.20 |
|---|---|
| 이분 매칭에 관한 몇 가지 반례들 (5) | 2022.07.16 |
| 표류 중인 어부 문제 (Lost Fisherman Problem) (0) | 2020.05.16 |
| C++ Windows 멀티스레딩 (0) | 2019.09.27 |
