[백준 1648번] 격자판 채우기 (Python3)

def makebit(bit):
  if len(bit) > N:
    return
  if len(bit) == N:
    bitlist.add(int(bit,2))
    return
  makebit(bit+"00")
  makebit(bit+"1")

def DFS(m,bit):
  if m == M-1:
    DP[m][bit] = int(bit in bitlist)
    return
  DP[m][bit] = 0
  for bit1 in bitlist:
    if bit1|bit != bit1:
      continue
    if DP[m+1][bit1-bit] == -1:
      DFS(m+1,bit1-bit)
    DP[m][bit] += DP[m+1][bit1-bit]
    DP[m][bit] %= 9901

N,M = map(int,input().split())
bitlist = set()
makebit("")

DP = [[-1]*(1<<N) for i in range(M)]
DFS(0,0)
print(DP[0][0])

비트마스킹 DP로 해결하였다.

처음 봤을때 풀이가 생각날듯 말듯 하면서 잘 안떠올랐던 문제였는데, 타일 채우기 [백준 2718번] 타일 채우기 (Python3) (tistory.com) 를 풀면서 영감을 얻고 해결할 수 있었다.

 

풀이방식은 타일채우기 문제와 비슷하다. 하지만 좀 더 일반화시켰다.

 

일단 타일 채우기 문제와 동일하게 현재 타일을 채울 때, 앞으로 한칸 삐져나오는 경우를 1, 삐져나오지 않는 경우를 0으로 두었다. 이때 타일을 채운 모양에서 0이 한개만 있어선 안된다. 예를 들어 타일이 1100으로 있다면, 00에는 타일 한개를 세로로 세워서 채울 수 있지만, 1101로 있다면, 0의 타일은 채울 수 없게 된다.

이러한 비트를 쉽게 구하는 방법이 있는지는 잘 모르겠지만 나 같은 경우에는 그냥 문자열로 해결하였다. (makebit 함수 참고)

 

그리고 비트마스킹을 이용한 DP를 이용하면 되는데, 이때 현재 비트와 다음비트에는 1이 겹쳐선 안되고 (이전에 삐져나왔다면 채울 수 없다) 현재비트와 다음비트를 합쳤을 때, 위에서 말한대로 0이 홀수개로 존재해선 안된다.

 

위의 조건에 맞는 비트로 이동하면서 DP를 하면, 최종적인 답을 구할 수 있다.

 

 

오늘의 교훈) 비트마스킹 DP를 적절하게 활용하자