[백준 1029번] 그림 교환 (Python3)

import sys
input = sys.stdin.readline

def DFS(cost,now,bit):
  if DP[cost][now][bit]:
    return
  for next in range(N):
    if bit&(1<<next):
      continue
    c = graph[now][next]
    if c < cost:
      continue
    if DP[c][next][bit|(1<<next)]==0:
      DFS(c,next,bit|(1<<next))
    DP[cost][now][bit] = max(DP[cost][now][bit],DP[c][next][bit|(1<<next)]+1)

N = int(input())
graph = []
for i in range(N):
  graph.append([*map(int,input().strip())])

DP = [[[0]*(1<<N) for i in range(N)] for i in range(10)]
DFS(0,0,1)
print(max(DP[0][0])+1)

비트마스킹 DP로 구현하였다.

사실상 외판원 순회 [백준 2098번] 외판원 순회 (Python3) (tistory.com) 문제와 거의 유사하다고 보면 된다.

 

살짝 다른점은 DP가 bit,N에서 추가로 cost까지 3차원 배열로 만들어야 한다는것이 다르다.

 

 

오늘의 교훈) 비트마스킹 DP는 유용하다.