BOJ 22847 공식풀이의 확장

나는 검수자로서, 대회 주최자로서 언젠가는 boj 22847 - 루미너스와 모험 중 마주친 퍼즐게임을 풀겠다는 의지를 잡고 있었다. 하지만, 엄두는 나지 않았다. 그와중에 주위에서 몇몇 분들이 풀겠다는 의지를 비쳤고, 그에 힘입어 나도 도전을 하였다. 

이 글을 루미너스의 공식 풀이를 본 분들에게 바칩니다...
공식 풀이에서 사용된 용어와 파트를 가지고 설명합니다. 

수도 없는 시간의 고민 끝에 나온 공식 풀이지만, 이를 구현하는 것은 너무나도 힘들 것 같았다. 특히 c 구역에 경우에 따라서 나누는 부분 앞에서 나는 구현할 의지를 잃었고, 그 경우를 하나로 통합하는 방법을 고민했다.

결론을 말하자면 C 구역에 D가 있는 모든 경우를 굉장히 비슷한 두 경우로 나누는 것에 성공했다. 이제부터 이에 대해 설명하려고 한다. 주의 사항은 사전 순으로 처음 오는 D를 잡고 이에 대해서 풀 것이다. (즉, C 구역에서는 내가 선택한 D의 왼쪽이나 위쪽에 다른 D가 존재하지 않는다.)

Case 1. 첫 D가 홀수번 째 열에 나왔다. 

1. 첫 D부터 위로 쭉 D를 지운다.
2. 위로 연결된 B 구역을 지운다.
3. 양쪽 직사각형을 지운다.
4. 두 줄 중에 D가 홀수개 있는 줄을 지우고, 나머지 한 줄을 지운다. 
그림으로 나타내면 아래와 같다. 

1번 행동은 선택한 D가 첫 D이기 때문에 위로 쭉 올라가면서 원래는 다 L이었기 때문에 바뀌어서 D가 되면서 지울 수 있다.
이에 인접한 2번 구역은 한 번 뒤집히는데, 공식 풀이 Case 3-3에 의해서 2번 구역의 두 함정은 같은 속성이었을 것이고, 1번 행동에 의해 한 번 뒤집어 졌으니 서로 다른 속성이 되어 둘 다 지울 수 있다. 
3-1과 3-2 둘 다 안에 속한 함정이 뒤집어진 총 횟수는 홀수 번이다. 이때 공식 풀이 Case 3-2에 의해서 원래 두 구역의 D의 개수는 홀수개였을 것이고, 홀수번 뒤집어졌으니 홀수개가 될 것이다. 따라서 두 구역 모두 지울 수 있다. 
최종적으로 4번 구역에는 D가 홀수개가 되며, 이는 4-1과 4-2 둘 중 하나의 라인에는 D가 홀수개 있다는 뜻이다. 따라서 그 줄을 지울 수 있으며 그 과정에서 다른 줄의 D가 홀수개가 되고, 지울 수 있다. 

Case 2. 첫 D가 짝수번 째 열에 나왔다. 

1. 첫 D부터 위로 쭉 D를 지운다.
2. 위로 연결된 B 구역을 지운다.
3. 1번과 닿아있지 않은쪽의 옆 직사각형을 지운다. 
4. 아래 연결된 B 구역을 지운다.
5. 나머지 옆 직사각형을 지운다.  
6. 두 줄 중에 D가 홀수개 있는 줄을 지우고, 나머지 한 줄을 지운다. 

 1번 행동은 선택한 D가 첫 D이기 때문에 위로 쭉 올라가면서 원래는 다 L이었기 때문에 바뀌어서 D가 되면서 지울 수 있다.
 이에 인접한 2번 구역은 한 번 뒤집히는데, 공식 풀이 Case 3-3에 의해서 2번 구역의 두 함정은 같은 속성이었을 것이고, 1번 행동에 의해 한 번 뒤집어 졌으니 서로 다른 속성이 되어 둘 다 지울 수 있다. 
  2번 구역에 의해서 한번 뒤집어진 쪽이 3번 구역이고 따라서 지울 수 있다. 
이에 연결된 아랫쪽 B 구역이 있고, 이 또한 한 번 뒤집혀졌기 때문에, 다른 속성이 되어 지울 수 있다.
 5번 구역은 1번과 2번 행동에 의해서 짝수번 뒤집어졌으며, 4번 행동에 의해 한 번 더 뒤집어졌다. 따라서 총 홀수번 뒤집어져서 지울 수 있다.
 최종적으로 6번 구역은 case1의 4번구역과 같은 방법으로 지울 수 있다. 

구현에 도움이 되었기를 바랍니다... Semi Game cup 화이팅!