[백준 2098번] 외판원 순회 (Python3)

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로 역추적하여 기록한다.

 

 

간단하지만 애초에 경우의 수가 너무 많은 문제이기 때문에, 방문 체크나 이런 것에서 하나라도 소홀히하면 바로 시간초과를 맞게되는 무시무시한 문제이다...

 

 

오늘의 교훈) 비트마스킹은 어렵다