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는 유용하다.