import sys
input = sys.stdin.readline
INF = 10**9
N = int(input())
graph = []
for i in range(N):
graph.append([*map(int,input().split())])
DP = [[-1]*N for i in range(1<<N)]
def DFS(bit,now):
if bit+1 == 1<<N:
if graph[now][0]:
DP[bit][now] = graph[now][0]
else:
DP[bit][now] = INF
return
if DP[bit][now] != -1:
return
for next in range(N):
if bit & 1<<next:
continue
if not graph[now][next]:
if DP[bit][now] == -1:
DP[bit][now] = INF
continue
DFS(bit|1<<next,next)
if DP[bit|1<<next][next] == INF:
if DP[bit][now] == -1:
DP[bit][now] = INF
continue
if DP[bit][now] > graph[now][next]+DP[bit|1<<next][next] or DP[bit][now] == -1:
DP[bit][now] = graph[now][next]+DP[bit|1<<next][next]
DFS(1,0)
print(DP[1][0])
DP + 비트마스킹 + DFS 문제이다.
무려 18번(!!) 의 틀렸습니다, 시간초과, 메모리초과 등등 끝에 결국 블로그 보고 참고해서 풀었다.
알고리즘을 요약하면 이러하다.
1. 2^N개의 DP list를 만든다.
2. 비트마스킹으로 지금까지 방문한 도시를 체크한다.
3. DP에는 현재 위치에서부터 나머지 모든 도시를 돌고 난 후 도착하는 최소거리를 DFS로 역추적하여 기록한다.
간단하지만 애초에 경우의 수가 너무 많은 문제이기 때문에, 방문 체크나 이런 것에서 하나라도 소홀히하면 바로 시간초과를 맞게되는 무시무시한 문제이다...
오늘의 교훈) 비트마스킹은 어렵다