[정리] 퍼즐 조각 채우기

table에 있는 조각들을 game_board의 빈 칸에 채워 넣으면 되는 문제입니다. 

제한 조건들이 있습니다. 정리해보면 1. 연속된 빈 칸에는 딱 맞는 조각만 채워 넣을 수 있으며 2. 좌우 대칭으로 조각을 바꾸는 것은 금지입니다. 3. table의 조각을 회전하여 game_board의 빈 칸에 맞출 수 있으면 인정입니다.

반환 값은 가장 많이 채워 넣은 빈 칸의 개수입니다.

더 얻어볼 수 있는 정보는 테이블은 모두 정방형 격자 모양이라는 사실과 0이 있으면 빈 칸, 1이 있으면 비어있지 않은 칸이라는 점입니다. C++을 사용하기 때문에 테이블의 상태는 이차원 벡터의 형태로 주어졌습니다.

또 한 가지 문제를 풀 때 늘 유념하는 것이 있는데 문제의 풀이가 복잡해지고 컨테이너 안에 또 다른 컨테이너가 있고 다시 또 컨테이너를 포함하는 등 어떤 오브젝트가 길고 이해하기 난해해지면 typedef을 적극 이용하거나 아예 Class을 정의해서 스스로 코드를 짤 때 헷갈리는 일을 방지하는 것입니다. 

Idea

game_board의 빈 칸과 table의 블록을 추출할 수 있으면 참 좋을 것 같습니다. 빈 칸을 나열하고 table에서 추출한 블록들 이리저리 돌려서 맞출 수 있다면 바로 정답을 찾을 수 있기 때문입니다. 그러면 table과 game_board 각각의 블록과 빈 공간을 추출하는 함수부터 만들면 됩니다.

이렇게 각 격자에 좌표 값을 줄 것입니다. 이것은 game_board이기 때문에 빈 칸을 좌표 값으로 나열하여 블록마다 묶으면 가령 (2,0)으로 시작하는 다섯 칸 짜리 빈 공간은 다음과 같은 표현으로 쓸 수 있습니다.

{(2,0), (3,0), (3,1), (3,2), (4,2)}

그러면 복잡한 생각을 제거하기 위해서 빈 공간을 하나의 Mesh라고 생각하고 각 격자는 Mesh을 이루고 있는 Vertex라고 생각하도록 합니다.

이 논리는 반대로 table에도 적용이 되어서 table에 놓여있는 블록들을 하나의 Mesh라고 가정하고 Mesh을 이루는 Vertex들이 격자라고 생각하도록 합니다.

figure 1a

초기 설계 단계에선 Vertex에 대해서 어떤 연산을 수행하게 될 지도 모르고 테스트도 해야 해서 필요하지 않은 연산자까지 Overload했습니다. 긴 Class이지만 실질적으로 가장 중요한 부분은 dobule x와 double y입니다. 이 Vertex Object 하나가 격자 하나를 대표하게 될 것입니다. 그렇다면 이 Vertex들이 모여서 만든 Mesh도 구성하는 것이 좋겠습니다.

figure 1b

Mesh class의 가장 중요한 부분은 Vertex을 원소로 갖는 벡터 vertices와 iterator입니다. iterator을 만들어 주면 나중에 STL Container로써 Algoritm library을 사용하기 간편합니다. Mesh는 Vertex들로 구성되어 있고 하나의 mesh object에는 Vertex들의 집합인 std::vector<Vertex> vertices가 있습니다.

이제 실질적으로 이들을 이용해서 game_board와 table로부터 유효한 블록/공백을 추출할 것입니다.

figure 1c

막상 코드를 구현하려 보면 한 가지 문제에 직면하게 됩니다. 어떤 Board로부터 블록을 추출하겠다는 문제를 해결하는 건 같지만 game_board와 table의 성질이 다릅니다. game_board로부터는 0으로 표기된 빈 공간을 추출해야 하지만 table로부터는 1로 표기된 채워진 격자를 추출해야 합니다. 이 둘은 똑같은 논리를 따라가지만 오직 이 한 가지만 다릅니다. 간단하게 코드를 복사하여 똑같이 두 함수를 만들면 되겠지만 별로 기쁜 방법은 아닙니다. (Code duplication)이 문제는 나중에 해결하도록 합시다.

일단 격자로부터 연속된 공간/블록을 찾는 것은 너비 우선 탐색 알고리즘을 활용하는 것이 최선일 것 같긴 한데 잘 모르겠습니다. 물론 다른 방법도 있겠지만 저로서는 떠오르는 방법이 없습니다. 

저는 y축을 기준으로 x축을 먼저 탐색하고 y+1축에서 x, x+1, x+2 , ... 이런 식으로 탐색을 했습니다. 그림으로 그려보면 다음과 같은 느낌으로 board을 탐색하게 될 것입니다.

figure 1c-0

parameters

figure 1c-1

int x와 int y은 현재 탐색 중인 격자의 좌표를 의미합니다. lv의 경우엔 어떤 예외를 막기 위해 고안했는데 만족스러운 방법은 아니었습니다. 이 예외는 실질적으로 Board을 탐색하는 함수와 함께 설명해야 합니다. 

figure 1c-2

 

(5,2)을 검증하고 난 이후 (6,2)을 검증하게 됩니다. 우리가 기대하는 것은 (5,2)까지 온 길을 다시 거꾸로 되돌아가서 최초의 탐색 시작점(Root)인 (3,0)으로 함수의 스택을 깨고 나오는 것입니다.

하지만 위의 코드를 보면 lv을 검증하지 않으면 재귀로 호출한 함수의 스택을 나오지 못하고 다음 For문을 돌기 시작합니다. 이는 치명적인 오류로 이어지기 때문에 현재 호출된 재귀의 함수 Level을 도입하여 더 이상 탐색할 격자가 없을 때, 최초의 ExtractBlock 함수 호출이 아니라면 스택을 깨고 나오도록 강제한 것입니다.

다른 효과적인 방법이 있을 것입니다.

함수의 호출 이후 가장 먼저 해야 할 일은 현재 탐색하려는 좌표의 x와 y의 값이 유효한지 검증하는 것입니다. 예를 들어서 탐색을 하다가 0보다 작은 좌표나 게임 보드의 최대 크기보다 큰 곳까지 탐색하는 경우를 막기 위함입니다.

vector board는 입력으로 받은 board의 값입니다. Parameter에 Policy라는 것이 보입니다. 이 부분엔 주어진 보드의 빈 공간을 추출할지 채워진 공간을 추출할지 결정하는 값을 넣어줄 것입니다. 이 ExtractBlock함수는 이 Policy에 의해 추출하는 값이 다릅니다.

figure 1c-3

이제 어떤 식으로 이 함수의 추출 방식을 조절할 수 있을지 고민해야 합니다. 저는 보드 내의 격자에 방문을 했는지 여부를 저장할 이차원 벡터 check_index을 만들었습니다. 이 벡터의 초기 값은 모두 False이며 구성할 수 있는 보드의 최대 크기 만큼 공간이 확보되어 있습니다.

figure 1c-4

이것을 활용하면 좋을 것 같습니다. 방문하지 않은 부분은 무조건 false입니다. 입력으로 주어진 최초의 game_board와 table(들을 아울러 이하 보드라고 표현)은 상태가 0과 1로 구성되어 있으며 0은 빈 공간, 1은 채워진 공간입니다. 우리는 보드를 탐색하기 위해서 충족해야 할 필수 조건이 있었습니다. 반드시 방문한 적이 없는 False여야만 한다는 점입니다.

또 현재 탐색하려는 격자가 반드시 비어있거나 반드시 채워져 있어야 하는 두 가지 상황이 있습니다. 처음 어떤 격자를 방문하게 되면 한쪽(check_ndex)은 언제나 False이지만 다른 한 쪽(game_board 또는 table)은 false와 true값 중 무엇이 나올지 확실히 알 수 없습니다. 다행히도 두 boolean을 연산했을 때 언제나 일관된 값을 얻어낼 수 있는 방법이 있습니다. 바로 XOR gate입니다. 운영체제 시간에 배운 것을 써먹을 때입니다.

Wikioedia에 XOR Gate부분을 참조하면 저런 표를 얻을 수 있습니다. C++는 XOR gate을 기호 ^으로 표기합니다. A가 보드의 각 격자의 상태라고 생각하고 B을 Policy라고 생각해봅시다. XOR gate는 쉽게 말해서 무조건 두 값이 같아야 false을 뱉습니다. Policy가 True면 격자가 채워진 상태를 추출한다고 가정하면 ( Policy(true) ^ (채워진 격자 = true) )= false을 얻을 수 있습니다. 한편으로는 Policy가 false이면 빈 격자를 찾는다고 하고 식을 세우면 ( Policy(false) ^ (빈 격자 = false) ) = false을 얻을 수 있습니다.

 

하지만 ( Policy(true) ^ (빈 격자 = false ) )= true이며 ( Policy(false) ^ (채워진 격자 = true ) )= true 입니다. 즉, Policy와 맞지 않는 격자를 선택하면 반드시 True가 나옵니다. 한편으로 우리가 격자를 탐색했는지 여부를 저장한 check_index는 언제나 탐색하지 않았을 경우 false을 내뱉기 때문에 다음과 같은 식으로 1. 탐색을 했는가? 2. 정책에 맞는 격자인가? 을 한 번에 검증할 수 있게 됩니다.

1c-5

Extract Block

figure 2a

검증이 끝났으면 각 보드를 탐색해도 안전하다는 확신이 듭니다. 어떤 식으로 좌표를 구성했는지 유념하면서 이중으로 For loop을 돌며 탐색을 시작합니다. i가 격자의 y, j가 격자의 x값입니다. check_index가 두 값이 반대인데 보드는 반드시 정방형이기 때문에 별 상관 없습니다.

figure 2b

XOR을 이용하여 방문하지 않았으면서 동시에 정책에 적합한 격자라는 판단이 서면 위와 같이 방문 여부에 체크를 해주고 임시로 이번 격자를 저장합니다. 밑에 네 개의 재귀 호출은 현재 격자를 기준으로 위아래, 좌우를 모두 탐색하게 되는데 예외 사항이 있기 때문에 네 방향을 모두 탐색해주는 것이 좋습니다. 만약 양의 방향으로만 탐색하면 다음과 같은 블록을 놓치게 됩니다.

이렇게 재귀를 한 바탕 돌고 나면 최소 한 개의 Mesh는 만들 수 있습니다.

figure 2c

figure 2d

그런데 문제가 있습니다. figure 2d의 lv을 검증하는 과정이 없으면 아무것도 없는 Mesh을 마치 찾은 것처럼 취급하는 오류가 생깁니다. 따라서, 아무것도 찾을 수 없었고 현재 Function call stack이 최초가 아니라면 멈추도록 해줍니다.

그 밑으로는 얻은 유효한 Mesh가 하나라도 있을 경우엔 정책에 따라 알맞은 컨테이너에 추가하도록 하는 코드입니다. 이제 정신이 아찔해지기 시작하는데 game_board_mesh는 game_board의 격자들을 Vertex화 시켜서 만든 Mesh을 저장한 컨테이너입니다. table_mesh역시 같은 원리로 만든 벡터입니다. 다시 말해서 game_board_mesh의 random access iterator을 호출하면 Mesh들이 뽑혀 나온다는 것입니다.

그렇게 추출한 Mesh을 성공적으로 각 벡터에 담았다면 temp_vertex는 재사용을 위해 0으로 초기화 해줍니다. 그렇게 For문을 모두 돌고 나면 정책에 따라서 보드의 빈 공간이든 뭐든 Mesh단위로 추출되어 다루기 아주 간편해집니다.

figure 2e

 

Rectify

이 문제를 풀기 힘들었던 것은 단순히 추출한 격자만 비교하면 되는 것이 아닙니다. 비교까지 거쳐야 할 난관들이 존재합니다. 이렇게 추출한 블록들은 제각기 다른 좌표 값을 때문에 비교를 진행하기가 어렵습니다. 그래서 블록들을 어떤 절대 공간 상에서 비교하면 편리할 것이라는 생각이 듭니다.

figure 3a

figure 3a의 두 블록은 분명 같은 모양이지만 좌표 값이 다르기 때문에 서로 같은 모양이라는 사실을 알아차리기 어렵습니다. 따라서 최대한 0을 기준으로 각 좌표를 변환할 것입니다.

figure 3b

예를 들어서 (2,0) (2,1), (1, 0), (3,0)으로 이루어진 Mesh가 있다고 가정해봅시다. 이 Mesh의 각 좌표 x와 y 값 중에서 가장 작은 값을 찾아서 다시 각 좌표에 빼준다면 Mesh가 최대한 (0,0)을 향해서 움직이게 됩니다.

(2,0) (2,1), (1, 0), (3,0)-> (1,0) (1,1), (0, 0), (2,0)

이렇게 추출한 모든 Mesh에 대해서 작업을 진행하면 엄청난 이득을 얻을 수 있는데 그것은 바로 정렬이 용이해져서 두 Mesh가 일치하는지 안 하는지 쉽게 알아낼 수 있다는 것입니다.

Rotatation

이번엔 회전입니다. 게임 보드의 구멍을 테이블의 블록으로 채울 수 있는 방법 중에서 회전도 포함되어 있습니다. 다행인 것은 회전의 각도가 90 degrees로 일정하다는 것입니다. 평면 좌표 상에서 어떤 점 (x,y)을 theta만큼 회전 시켜 (x`,y`)을 얻는 것은 어렵지 않습니다.

이전에 사용했던 그림입니다

그런데 큰 문제가 있습니다. 바로 cos ( pi radians ) 에 대한 것입니다. C++는 sin, cos, tan 등등 Trigonometry에서 Degrees가 아닌 Radians을 사용합니다. pi라는 값이 무리수이기 때문에 코사인 함수를 그린 좌표계 상에서 pi값이 흔히 x = pi일 때 y가 0으로 딱 떨어지는 것 같지만 실은 x = 3.14......언저리로 무한히 근접하는 어떤 수에 대한 기대하지 않은 값을 얻게 됩니다. 따라서 우리가 주기 함수로써 sine cosine을 그리는 것처럼 x = pi radians일 때 0으로 떨어지는 상황을 C++에서 구현하기는 힘듭니다. 이 부분에 대해선 따로 처리를 해줘야 합니다. M_PI는 <cmath> 또는 <math.h> 헤더 파일을 불러오기 전에 사용하겠다는 의미에서 다음과 같은 문장을 앞서 해줘야 합니다.

figure 3c

figure 3d

입력되는 각이 0부터 360 Degrees라는 걸 알기 때문에 무한한 범위에 대해서 예외 처리하지는 않았습니다. 다만 GCC/G++ complier에서는 실수에 대한 모듈로 함수 fmodl이 std:: namespace에 없다고 할 수 있기 때문에 std::을 빼주어야 합니다. sine cosine에 대한 처리도 끝났으니 이제 Mesh을 받아서 회전 시키는 함수를 만들어야 합니다.

figure 3e

위처럼 어떤 Mesh을 받으면 해당 Mesh을 90degrees씩 네 번 회전하여 새로운 Mesh을 만들고 Mesh을 담는 컨테이너 Meshes에 저장하여 반환합니다. 이러면 입력 받은 Mesh가 90, 180, 270, 360 degrees가 돌아간 네 개의 새로운 Mesh들을 얻을 수 있습니다.

Sort

Algorith의 Library엔 Sort가 있습니다. 사실 Iterator을 만든 이유가 이걸 사용해서 편하게 문제를 풀고 싶었기 때문인데 생각보다 쉽지 않았습니다. 따라서 Mesh가 갖고 있는 Vertex들끼리 정렬을 수행할 함수를 구현했습니다.

figure 4a

알고리즘을 공부하면서 배운 정렬입니다. pivot을 어디에 둘 지 고민을 좀 했는데 Vertex의 개수가 천문학적으로 많을 것 같지는 않기 때문에 무조건 끝 쪽으로 잡았습니다. 정렬 기준은 x가장 우선이고 그 다음이 y입니다.

figure 3b의 Rectify의 끝에 SortMesh함수가 있는데 이유는 간단합니다. 어차피 회전을 한 vertex는 (0,0)을 축으로 회전하기 때문에 각 Vertex가 (0,0)에서 멀어지게 됩니다. 따라서 다시 (0,0)을 향해 모든 Vertex을 움직일 필요도 있고 비교를 위해서 정렬을 할 필요도 있으니 정렬 함수를 Rectify에 넣어서 한 번에 처리한 것입니다.

Process Board

이제 마지막 단계입니다. 이렇게 각 보드에서 정책에 맞게 추출한 블록들을 비교하여 빈 공간에 몇 개의 블록을 끼울 수 있는지 비교할 것입니다.

figure 5a

가장 먼저 정답을 반환할 answer을 선언합니다. 그리고 game_erased와 table_erased는 문제가 내포한 함정을 피하기 위해 만들었습니다.

예를 들어서 3번 블록 같은 경우엔 game_board에 들어갈 수 있는 구멍이 두 개 존재합니다. 왜냐하면 이 3번 블록은 회전을 시키게 되면 game_board의 구멍과 똑같은 모양이기 때문입니다. 하지만 문제에서는 table의 블록을 하나 소모하면 더 이상 계산을 할 수 없어야 합니다. 

반대로 table에 3번 블록이 두 개 이상 존재하고 game_board에 해당 블록에 맞는 구멍이 단 하나밖에 없다면 table에 블록을 소모하여 막으면 더 이상 game_board에 맞는 블록이라할지라도 더 이상 사용할 수 없어야 합니다.

 

game_erased와 table_erased의 크기는 game_board와 table에서 추출한 Mesh들의 개수이며 그 값은 모두 false 즉 지워지지 않았다는 뜻으로 초기화 했습니다.

처음에는 std::remove_if나 std::find을 사용하여 사용한 블록 자체를 지워버려서 비교 연산의 횟수를 줄이는 방향으로 설계를 했지만 너무 복잡해져서 다른 방법을 선택했습니다.

for문이 진짜로 비교를 진행하는 부분입니다. game_board의 구멍에 대해서 table의 Mesh을 회전시켜서 해당 모양과 일치한다면 game_board와 table에서 해당 부분을 제거합니다. 이 제거의 표현은 game_erased와 table_erased의 값을 true로 바꾸는 것으로 대체합니다.

figure 5b

두 Mesh가 서로 완전히 같으려면 Mesh을 구성하는 Vertices가 크기부터 시작해서 완전히 같아야 합니다. 그것을 표현한 함수입니다. 만약 두 Mesh가 완전히 같다면 문제에서 묻는 것처럼 game_table의 빈 칸 중 채워진 개수를 답으로 내놓아야 합니다. 따라서 figure 5a에서 보는 것처럼 answer에 현재 검증 중에 있는 Mesh의 vertex의 개수를 합해야 합니다. 왜냐하면 vertex을 초기에 하나의 격자라고 했고 이 격자가 문제에서 처음 제시된 0 또는 1로 구성된 구멍이기 때문입니다.

이제 모든 것이 끝났습니다. 구현한 함수들을 적당히 배치해서 입력을 받는 대로 메꾼 구멍의 개수를 정답으로 내놓으면 그만입니다.

figure 5c 

먼저 game_board의 구멍을 추출하고 game_board을 추출하며 중고가 된 check_index을 새롭게 초기화 합니다. 다시 table에 대해서 추출을 하고 추출한 Mesh을 담은 game_board_mesh와 table_mesh을 (0,0)기준으로 정렬을 합니다.

마지막으로 추출한 mesh들을 비교하여 답을 내놓으면 끝입니다.

잘 됩니다

 

Futhermore

이 문제를 풀 때 이상한 점이 있었습니다. 예외가 있을 것 같은 테스트 케이스를 아무 생각 없이 만들었습니다.

이것을 문제에서 제시하는 것처럼 입력 값으로 만들면 다음과 같습니다.

game_board =

[0, 0, 1, 0, 0]

[0, 0, 1, 0, 1]

[0, 1, 0, 1, 0]

[1, 0, 0, 1, 0]

[0, 1, 1, 0, 0]

table =

[0, 1, 1, 0, 0]

[0, 0, 1, 1, 0]

[0, 1, 0, 0, 1]

[0, 1, 0, 1, 1]

[1, 1, 0, 1, 1]

어찌된 영문인지 이 테스트 케이스는 실패합니다. 왜 기댓값이 0이어야 하는지는 잘 모르겠습니다.