[PS?] 루미큐브(Rummikub)의 경우의 수를 컴퓨터로 계산해 보자

https://namu.wiki/w/%EB%A3%A8%EB%AF%B8%ED%81%90%EB%B8%8C

루미큐브 - 나무위키

 군대에 있으면서 코로나로 휴가도 못나가는 이 상황에서 우리들이 할 수 있는 건 보드게임 같은 시간 보내기 류 들이다. 정식 룰로 하지는 않는 것 같다. 그래서 아무튼 자주 루미큐브를 하는데 계속 내 마음대로 안되고 지는 것 같아서 상당히 화가 났다.

 

 그래서 이 억울함을 해결하기 위하여 어떻게든 생각을 해 보았는데, 루미큐브에 있어서 가장 중요한 것은 조합을 생각해 내는 것 이라고 생각한다. 그런데 하다 보니까 이게 삼성 A형 기출을 풀다 보니까 최근에 푼 문제들(색종이 겹치기라든가, 야구 문제라든가)이랑 상당한 유사성(완전탐색인데 구현을 요하는 완탐)이 있는 것 같아서 한 3시간 정도 생각해서 코드를 짜 보았다.

 

 

 그리고 완벽하게 작동하는걸 볼 수 있었다! (PS를 실제로 써먹을 줄이야) 하지만 단점이라고 하자면, 실제 게임에서 할때는 무슨 카드가 몇개 있는지 일일히 세서 노트에 써가면서 기록하고 또 그걸 매 턴마다 핸드폰에서 repl.it로 INPUT값을 바꿔주며 실행시키니까 내 턴에서 시간이 너무 오래 걸린다는 단점이 있었다. 또, 프로그램을 실제로 돌리는 데에도 시간이 은근 오래 걸렸다. 탐색 시간이 오래 걸리면 걸릴수록 게임을 끝낼 수 있다는 기대감은 커지지만(가능 하니까 끝까지 계산하겠지? ㅋㅋ), 가능한 조합이 없다고 뜨면 좀 실망스럽다. 장점은 끝낼 수 있는데 모르고 못 끝내서 넘어가는 경우가 없다는것. 적어도 억울하진 않다. (예상치 못한 원턴킬)

문제 해결 전략

 입/출력은 깃헙에 잘 나와있습니다. 근데 조커는 고려 안함.

 

 일단 DFS()를 활용한 완전 탐색인데, 진짜 다른 완전 탐색이랑 비슷하다. 다만 어려웠던 점은 구현하는 방법이 제일 어려웠다. 탐색을 하는 우선 순위는 색은 검 빨 노 파 순(색깔은 임의 지정)으로, 숫자는 오름차순으로 정했다. 2개가 있을 수 있기 때문에 탐색 시작점은 매개변수로 받지 않고 시작 할때마다 계속 새로 찾아서 지정했다.(특정 카드를 했다고 지나 갔는데 그 카드가 또 있을 수 있기 때문)

 

 그리고 그 뒤로는 간단하다. 조합에는 2가지가 있다. 같은 색 오름차순 나열(3개 이상)과 같은 숫자 다른색 나열(3개 이상) 으로 구분해서 각각 조합을 구하고 진행하면 된다. 기저 경우(Base Case)는 남은 카드가 있는지 확인하고 없으면 하나의 조합 경우의 수가 완성이 된 것이다. 그래서 조합 출력으로 끝. 이런 식으로 반복을 할 수 있다.

 

 조커를 제외한 루미큐브 모든 카드(각 숫자, 색 2개씩 13 * 4 * 2 = 총 104개)의 경우의 수는 6,115,406가지이다.(사실 계산하다가 중간에 자리를 비웠다가 다시 봐서 정확하게 계산 한건지 아니면 중간에 멈춘건지는 모르겠음) 계산하는데 생각보다 오래 걸렸는데, 이걸 최적화를 하면? 천재인듯;;(설마 완탐 말고 다른게?)

코드

https://github.com/december-ok/Rummikub

december-ok/Rummikub