알고리즘 Study 에서 이번에 BlockGame이라는 문제를 풀게 되었습니다.
https://algospot.com/judge/problem/read/BLOCKGAME
인데요, 풀이의 포인트는 다음의 두 가지로 정리됩니다.
1. 전수조사
3칸 or 2칸 block 을 골라야 하지만 편의상 2칸의 block만을 고른다고 할 때 대략
25C2 * 23C2 * 21C2 ... 3C2 입니다.
모든 경우에 3칸도 고를 수 있다고 치면 2를 매번 곱하면 되므로 2^12를 추가로 곱해주면 될 것 같네요.
3786916514485104000000L * 2^12 = 15511210043330985984000000L
정도의 경우의 수가 나오므로 이걸 다 저장하고 계산하는 것은 무리입니다.
하지만, [1,1,1,1,0] 이 [1,1,0,0,0] 다음에 생성되거나,[0,0,1,1,0] 다음에 생성되거나 결과는 동일하므로 순서가 중요하지 않고 검사 할 당시 배열의 상태만이 중요합니다. (설명을 위하여 1차원 배열로 기술하였으나 실제로는 2차원 배열)
즉, 가능한 모든 Board의 모양은 2^25 보다 적을 것 입니다.
2^25 는 33554432 이므로 이 정도라면 저장 할 수 있습니다.
즉, 메모이제이션을 쓴다면 탐색 시간이 아주 짧아지겠죠.
2. Bitmasking
문제를 풀기 위한 함수가 최대 2^25번 호출된다고 하면, 이 함수를 최대한 간소화해서 짜야 합니다. 이점을 간과하고 처음에는 5x5의 board에 block이 들어가는지 확인하기 위해 다음과 같은 코드를 짰습니다.
def canPush(self, board, pushBoard):
for x in range(len(board)):
for y in range(len(board[0])):
if 1 == pushBoard[x][y]:
if board[x][y] != 0:
return False
return True
그냥 단순하게 5*5 번의 loop을 돌며 두 board (두번째 board는 block이라고 보시면 됩니다) 를 비교하는 code인데 이것이 상당한 cost가 되더군요.
이를 사용한 코드는 대략 는 이렇습니다.
for block in totalBlock:
if self.canPush(board, block):
...
별것 아닌 것 같은데 이 경우 시간이 너무 오래 걸렸습니다.
이를 해결하기 위해서 bitmask 를 사용합니다.
즉, 5x5 배열이 어짜피 1 혹은 0으로 표시 될 수 있으므로 이를 AND나 OR 연산으로 한번에 비교하는 것 입니다. 다음과 같습니다.
for block in totalBlock:
if block & board == 0:
if not self.isWin(board | block, totalBlock):
이렇게 하면 획기적으로 속도가 빨라지더군요-
설명한 1과 2를 이용한 전체 코드는 다음과 같습니다.
def isWin(self, board, totalBlock):
self.callCnt = self.callCnt + 1
ret = False
if board in self.boardMap:
self.hitCnt = self.hitCnt + 1
ret = self.boardMap[board]
return ret
for block in totalBlock:
if block & board == 0:
if not self.isWin(board | block, totalBlock):
ret = True
break
self.boardMap[board] = ret
return ret
자 그럼 이 경우 문제가 풀렸느냐
그렇지 않습니다.
...ㅠㅠ
Python에서 제귀 자체에 대한 비용이 꽤 큰지 탐색 할 경우가 많으면, 제대로 풀리지 않았습니다.
일단 pypy를 사용해봤는데요, 정말 획기적으로 속도 향상이 있었지만 문제가 되는 케이스에서는 여전히 만족할 속도가 나오지 않았습니다.
대략적으로 python에서 50여초가 걸리던 케이스가 pypy에서는 9초가 걸리더군요-
우선 개선점을 좀 더 고민하다가, board가 저장되면 이를 90도, 180도, 270도 돌린 board도 결과가 같음을 알았습니다.
저장하는 부분 self.boardMap[board] = ret 에 위의 3가지 케이스가 더해지도록 합니다.
우선 회전을 위한 코드는 다음과 같습니다.
def rotate5x5(self, board):
while len(board) < 25:
board = "0" + board
rotated = [0 for i in range(25)]
rotatedIdx = [[i+j*5 for i in range(5)] for j in range(5)]
rotatedIdx = [list(tmp) for tmp in zip(*rotatedIdx[::-1])] # Rotate
rotatedIdx = [item for sublist in rotatedIdx for item in sublist] # to Flat
for idx in range(25):
rotated[idx] = board[rotatedIdx[idx]]
return rotated
이를 활용해서 저장부에 다음을 추가합니다.
rotated = self.rotate5x5("{0:b}".format(board)) # 90
self.boardMap[int("".join(rotated), 2)] = ret
rotated = self.rotate5x5("".join(rotated)) # 180
self.boardMap[int("".join(rotated), 2)] = ret
rotated = self.rotate5x5("".join(rotated)) # 270
self.boardMap[int("".join(rotated), 2)] = ret
자- 잘 풀렸을까요?
아닙니다. isWin의 cost가 rotate5x5로 인해 늘어나서 속도는 더 느려집니다. ㅠㅠ
rotate5x5의 연산 cost를 다음과 같이 좀 무식하게 해서 줄여봤습니다.
while len(board) < 25:
board = "0" + board
rotated = [0 for i in range(25)]
rotated[0] = board[20]
rotated[1] = board[15]
rotated[2] = board[10]
rotated[3] = board[5]
rotated[4] = board[0]
rotated[5] = board[21]
rotated[6] = board[16]
rotated[7] = board[11]
rotated[8] = board[6]
rotated[9] = board[1]
rotated[10] = board[22]
rotated[11] = board[17]
rotated[12] = board[12]
rotated[13] = board[7]
rotated[14] = board[2]
rotated[15] = board[23]
rotated[16] = board[18]
rotated[17] = board[13]
rotated[18] = board[8]
rotated[19] = board[3]
rotated[20] = board[24]
rotated[21] = board[19]
rotated[22] = board[14]
rotated[23] = board[9]
rotated[24] = board[4]
return rotated
조금 줄어들긴 합니다만, 여전히 안쓰는 것 보다 더 높은 cost 를 요구합니다 ㅠㅠ
즉, bit 연산처럼 O(1) 의 cost로 배열을 돌릴 수 없다면, 5x5의 경우 그다지 성능 개선이 나오지 않습니다. (물론 더 커지면 의미가 있을 것 같네요)
아무래도 그냥 메모이제이션만 사용하는게 우선은 최선이라 할 수 있겠네요.
즉, 이 문제는 python으로는 무리가 있는 것 같습니다.
(해결하신 분은 저도 알려주세요. 계속 고민해봐야죠.)
여기서 궁금증이 생겨서 python(그리고 pypy)의 recursion cost를 측정해봤습니다.
재미있는 점은 변수도 cost에 큰 영향을 준 점인데요, 아래의 코드에서 callCnt가 그것입니다.(callCnt는 굳이 이렇게 측정하지 않아도 2^n이지만 비교를 위해 넣습니다) 일단 코드는 다음과 같습니다.
callCnt = 0
def cost(self, n):
self.callCnt = self.callCnt + 1
if n == 0:
return 1
else:
return self.cost(n-1) + self.cost(n-1)
def testRecursion(self):
self.cost(20)
print self.callCnt
이를 돌리면 python에서는 0.640529870987 의 시간이 걸립니다.
pypy에서는 어떨까요? 0.121232032776 가 걸리네요-
재미있는 점은 위에서 self.cost(20)이 아닌 5와 같이 작은 수로 한 경우인데요,
이 경우 pypy가 더 느립니다.
pypy: 0.000104904174805
python: 5.60283660889e-05
10정도 해도 pypy가 더 느리네요.
pypy: 0.016s
python: 0.001s
아마 pypy의 최적화 코드가 어느정도 까지는 오버해드로 작용하는 것 같습니다.
사용한 python은 Python 2.7.6 이며, pypy는 Python 2.7.3(PyPy 2.2.1 with GCC 4.8.4) 입니다.
