소코반 구현해 보기 : 맵 상태를 쪼개면 답이 보인다.

 구현 8번째 시간입니다. 실전 문제 하나를 풀면서, 여러 가지 기법들을 다뤄보겠습니다. 소코반 게임은 캐릭터와 박스가 있습니다. 이 박스들을 적절히 목표 지점에 이동시켜야 하는 게임입니다. 아. 옛날에 많이 있었던 게임 중 하나입니다. 그냥, 우리는 캐릭터를 명령에 맞게 이동시킨 다음에 맵의 상태를 출력하는 것이 목표라면 목표라고 할 수 있겠네요.

 

 그런데, 맵의 상태를 보니까, 목표 지점에 있는 ~가 눈에 보입니다. 즉, 목표 지점이면서 박스가 있는 곳이라던지, 목표 지점이면서 캐릭터가 있는 곳이라던지. 즉, A and B 조건이 눈에 밟힙니다. 이렇게 되어버리면 경우의 수를 처리해야 할 것이 상당히 많아집니다. 이것을 적절히 분해를 해서 처리를 하는 방법을 고민해 봅시다. 물론, 제 코드를 조금 더 응용하시면 실제 소코반 게임을 만들 수도 있을 거에요. 키보드 이벤트라던지 GUI 정도만 더 들어가면 되니까요.

 

 

---

 일단 2가지 맵으로 분해를 해 봅시다.

 

 

 그러면, 캐릭터가 이동했을 때 어느 맵만 건드리면 될까요? character가 이동해도, 벽과 목표 지점, 빈 공간은 변하지 않습니다. 그렇다면, <벽, 빈 공간, 박스, 캐릭터> 만 적절하게 이동시키면 될 거에요.

 

 

 즉, 캐릭터가 움직이면, 노란색 부분만 변하게 하면 됩니다. 그리고 상태 또한 상대적으로 간단합니다. 목표 지점 생각하지 않고, 그냥 캐릭터와 box만 적절하게 잘 이동이 되면 되기 때문입니다. 이걸 토대로 map을 2개의 맵으로 분해하면 아래와 같이 코딩할 수 있습니다.

 

 

 먼저, 목표 지점, 벽, 목표지점이 아닌 빈 공간입니다. 사실 간략화를 위해서, 그냥 목표지점이면 '+'이고, 아니라면 '.'로 처리해도 무난합니다. 결국 해당 지점에 놓았을 때, 목표점이 가려지는지가 중요하기 때문입니다. 저는 벽이면 '#', 그렇지 않고 목표점이면 '+', 그게 아니라면 '.'로 처리했습니다.

 

 

 그 다음에 real_box는 상자, 캐릭터, 빈 공간, 벽만을 표현합니다. 각각 'B', 'W', '.', '#'로 나타낼 수 있습니다. 이 경우, character가 한 번 이동한 경우, 이 배열만 변형시키면 된다는 것을 알 수 있습니다.

 

 

---

 다음에 character의 현재 위치를 찾고 시작합니다.

 

 

 이동 방향 1칸을 갔을 때, 캐릭터가 위치할 지점을 tx, ty라고 해 봅시다. 이 지점이 Empty한 경우에는 그냥 캐릭터는 그 지점으로 이동하면 됩니다. 그런데, 그 상태를 어떻게 판단해야 할까요? 이미 맵은 2개나 물려 있습니다. state(x,y)는 x,y의 실제 상태를 리턴해 주는 함수입니다. 이는 분해의 역과정으로 진행하면 됩니다. 먼저 real_box는 박스, 캐릭터, 빈 공간, 벽 상태였은이까, 그걸 기준으로 봅시다.

 

 

 먼저 real_box[x][y]가 벽이다. 그러면 벽을 리턴해 주면 됩니다. 박스이거나, 캐릭터이다. 그러면 이야기가 조금 달라지는데요. 목표 지점에 있느냐, 그렇지 않느냐에 따라서 상태가 달라질 수 있기 때문입니다. 예를 들어, real_box[x][y]의 상태가 'W'였는데, 캐릭터가 목표 지점에 있지 않았다면, 실제 [x][y]의 상태는 'w'일 겁니다.

 

 

 만약에, 그렇지도 않다면, real_map[x][y]가 목표 지점인지 판단합니다. 박스가 있거나 캐릭터가 있거나 벽이지 않기 때문입니다. 그러면, 기본적으로 빈 공간이라는 건데요. 목표지점이면서 비었거나, 그냥 비었거나. 둘 중 하나입니다. 이 경우 real_map[x][y]를 참조하면 됩니다. 이 값이 '+'인지 아닌지에 따라서, 다른 값을 리턴하면 됩니다.

 

 

---

 한 가지 문제가 남아 있습니다. 박스가 가장자리에 있는 경우에는 어떨까요?

 

 

  예를 들어, 현재 내가 있는 위치가 <x,y>이고, 그 윗 방향에 'B', 박스가 있는데 그 곳이 가장자리인 경우입니다. 그런데, 문제 조건에 의하면, 가장 자리에 있는 곳은 항상 벽이므로, 이러한 경우는 없습니다. 심지어 빈 공간이 가장 자리에 있는 경우도 없으니, 마음 놓고 이동을 시켜도 됩니다. 

 

 

  이동을 할 공간 (tx,ty)가 빈 공간이거나 WALL인 경우, 그냥 이동시키면 됩니다. 37번째 줄을 보시면, 내가 이동할 공간이 Empty인 경우, 적절하게 이동하고 있음을 알 수 있습니다. 그런데, Box가 있는 경우는 이야기가 달라질 수 있습니다. 이 때에는 캐릭터, 박스, 빈 공간인지, 아니면 캐릭터, 박스, 벽/박스인지 구분을 해야 합니다.

 

 

 이는 (tx,ty)로부터 내가 이동하려는 방향으로 1칸 더 이동한 (tx2,ty2)의 상태를 보면 알 수 있습니다. 만약에 (tx2,ty2)도 빈 상태라면, Box는 (tx2,ty2)로, 캐릭터는 (tx,ty)로 move하면 될 겁니다. 그런데, 우리는 간과한 조건이 하나 더 있습니다. 만약에, 중간에 끝난 경우는 어떻게 해야 할까요?

 

 

 그렇다면 목표점에 도달하지 못한 box가 있으면 안 됩니다. 이 상태는 'b'였습니다. 혹은 '+'가 있으면 안 될 거에요. 이것은 캐릭터도, 박스도 위치하지 않은 목표점이기 때문입니다. 이 두 상태 중 하나가, nm칸의 좌표를 돌면서 단 하나라도 있으면, complete 된 상태가 아닙니다.

 

 

 이렇게 다 돌고 나서 map 상태와, 게임이 완료 되었는지를 출력하면 됩니다. 이것을 모두 적용한 코드는 제 github의 BOJ 폴더의 4577.c에 있습니다. 이제 쉬운 것 같지만 상당히 중요한 과제를 드리겠습니다.