안녕하세요. chogahui05입니다. 저번 시간에 소코반을 구현해 보았습니다. 다소 어려웠어요. 오늘은 그것보다 다소 쉬운 2048 퍼즐의 1턴을 구현해 보도록 하겠습니다. 사실 뿌요뿌요 게임도 구현해 보면 재밌긴 합니다. 그런데 그건 BFS, DFS를 알아야 하는 전제가 깔리니 쉽지 않긴 하지만요. 하튼, 구현해 봅시다.
2048은 어떠한 것을 합칠 수 있는 방향이, 위, 아래, 왼쪽, 오른쪽이 있습니다.
이 중, 퍼즐이 요렇게 있고, 우측으로 합친다고 해 봅시다. 그러면, 먼저 2와 2가 merge 될 거에요.
다음에 노란색 4와 파란색 4는 merge 되지 않아요. 단지, 파란색 4끼리만 merge가 됩니다.
이렇게 합쳐질 겁니다. 다음에 8과 4를 합치려니, 되지 않습니다. right 명령을 내린 경우, 여기서 끝이 납니다. 그러면, right 명령어가 들어왔을 때에는 각 행마다, 블록에 있는 수들의 정보를 읽어내서 merge를 하면 될 거에요.
단지, 읽는 방향이 오른쪽에서 왼쪽이였을 뿐입니다. left로 merge 하면 어떨까요?
읽는 방향을 좌에서 우로 보면 됩니다. down 방향인 경우 각 열별로 아래에서 위로, up 방향인 경우, 열별로 위에서 아래 방향으로 읽어내면 되겠죠.
그러면, 이 읽어낸 정보를 어떻게 가공해서 다시 넣으면 좋을까요?
예를 들어, Right 방향으로 합치라는 명령이 떨어진 경우, 각 행마다 우측에서 좌측으로 읽어내면 될 거에요. 그렇다면 각 블록이 합쳐지냐, 그렇지 않느냐를 판단할 때 가장 중요한 factor가 무엇인가요? 이전에 MERGE가 되었는지, 그리고 현재 BLOCK의 사이즈일 거에요. 이 둘을 잘 저장해 봅시다.
여기서 sz는 현재 block의 size, merge는 합쳐졌는지에 대한 여부입니다. 그런데 중간에 0이 있는 경우에는 어떻게 해야 할까요?
그런 거 그냥 무시하면 됩니다. 0이 있다고 한들, 2와 2는 합쳐질 수 있기 때문입니다.
그러면 노란색 부분만 정보에 잘 넣으면 될 겁니다. 이 정보를 넣은 자료구조를 v라 합시다. 이 때 우리는 블록의 크기와 merge 되었는지를 넣을 건데요. 초기에는 어떤 block이던 MERGE가 되어 있지 않으므로, merge flag는 0으로 set 합니다.
그러면 v에는 다음과 같은 내용이 들어갈 거에요. 여기서 u를 build 해 봅시다. u는 merge한 결과물을 저장합니다.
먼저 1번째 원소는 무조건 add 합니다. 다음에 2번째 원소와, u의 맨 뒤에 있는, 그러니까 보라색으로 칠한 원소를 보겠습니다.
보라색과 노란색 부분입니다. 이 둘이 Merge 조건을 만족하는 경우에는 u에서 원소 하나를 빼고, 4로 Merge 되었다는 새로운 정보를 넣어주면 됩니다. 그러면 요렇게 될 거에요.
다음에 3번째 원소와, u의 맨 뒤에 있는 것과 비교합니다. 그러면 이것은 합쳐질 수 있나요? 아닙니다. 크기는 같지만, 합쳐진 BLOCK이 있기 때문에, 합쳐지지 못합니다.
그러니 이렇게 될 거에요. 이제 u의 맨 뒤에 부분과 v의 4번째 원소를 합칠 수 있는지 봅시다. 크기도 같고, 둘 다 합쳐지지 않았어요. 따라서, 이 둘을 Merge 하면 좋겠습니다. 그러면 보라색으로 칠한 것이 pop이 되고, 8, M = 1이라는 정보가 새로 들어올 거에요.
다음에 v의 5번째 원소와, u의 맨 마지막 원소를 봅시다. 합쳐질 수 있나요? 아닙니다. 따라서 u의 맨 뒤에 노란색 정보를 추가합니다.
그러면, u vector에는 크기가 4, 4, 8인 블록이 차례대로 있다는 정보를 얻을 수 있습니다. 이것을 어떤 순서대로 채우면 좋을까요? 읽어낸 방향으로 채우면 됩니다.
나머지 부분은 모두 0으로 채우면 됩니다.
이것을 그대로 코드로 구현하면 위와 같습니다. 그리고, left, right, down, top으로 밀어라라는 명령이 들어온 경우, 읽어내는 방향만 잘 정하면 build 함수를 잘 호출하면 된다는 것을 알 수 있습니다.
예를 들자면, right 함수는 이렇게 작성하면 됩니다. left, up, down도 크게 다를 바 없어요. 그런데, 그 기능을 모두 구현하자고 16줄이나 되는 함수 4개를 따로 따로 구현할 필요가 있을까요?
실제로 12209.cpp 소스를 보시면 아실 수 있듯, 이것은 코드가 지저분해지는 원인이 됩니다. 기능이 겹치는데 왜 굳이 따로 선언을 해야 할까요? 사실 달라 보일 수 있어요. 그런데, 2048 퍼즐의 배열을 적절히 변형시키고, 한 방향으로만 밀어버린다고 가정한다면 생각보다 수월하게 문제가 풀릴 수 있어요.
예를 들어, DOWN 방향으로 밀어야만 한다고 가정해 봅시다. 그 경우, RIGHT 방향으로 밀어야 한다는 OPERATION이 들어온 경우에 어떻게 해야 할까요?
먼저, 원본 배열을 90도 시계 방향으로 회전시킵니다. 그 다음에 그 array를 아래 방향으로 Merge를 시킨 후에, 결과 배열을 90도 시계 방향으로 3번 회전시키면 됩니다. 만약에 LEFT OPERATION이 들어오면 어떨까요?
그러면 시계 방향으로 3번 회전시키고, 변형된 배열을 아래쪽으로 밀어버리는 DOWN 연산을 수행한 뒤에, 변형된 배열을 다시 90도 시계 방향으로 회전시키면 됩니다. 최소한 TOP, RIGHT, LEFT를 16줄을 쓸 정도로 복잡하게 구현을 하지 않아도 됩니다. 이 방법은, 제 코드를 짧고 명확하게 해 줄 수 있을 거에요.
자. 제 12209.c 코드를 보다 깔끔하고 명확한 코드로 바꿔주세요.
'구현' 카테고리의 다른 글
| 백준 16768 : 뿌요뿌요 게임을 구현해 봅시다. (10) | 2020.01.27 |
|---|---|
| 코딩 테스트 통과를 위한 세세한 제한 조건 잘 읽기 (10) | 2020.01.03 |
| 소코반 구현해 보기 : 맵 상태를 쪼개면 답이 보인다. (2) | 2019.12.09 |
| bit 연산 : on/off 상태가 20개 언저리면 고려해 보자 (0) | 2019.11.10 |
| quento 퍼즐 문제 : 백 트래킹으로 풀어봅시다. (4) | 2019.11.02 |
최근댓글