백준 2098 - 외판원 순회 (Python)

너무 어려워 다른 분들의 풀이를 참고했던 문제입니다.
비트마스크, 동적프로그래밍, dfs가 섞인 문제입니다.

dp에 적용한 점화식은 아래와 같습니다.

dp[now][visited] = min(dp[now][visited], dfs(i, visited | (1 << i)) + graph[now][i])

dp[0][0001] = dp[0][1]
현재 0에 위치해 있고 1을 방문했으며 앞으로 2 3 4 를 방문한 다음에 다시 0으로 돌아오는 최솟값입니다.

나머지 부분은 직접 코드로 보시면 이해하기 편하실 겁니다.

import sys

input = sys.stdin.readline
INF = float('inf')

n = int(input())
dp = [[INF] * (1 << n) for _ in range(n)]

def dfs(now, visited):
    # 0에서 시작해 모든 경로를 돌았으니 현재 위치에서 0으로 가는 길을 반환
    if visited == (1 << n) - 1:
        if graph[now][0]:
            return graph[now][0]
        else:
            return INF

    if dp[now][visited] != INF:
        return dp[now][visited]

    for i in range(1, n):
        if graph[now][i] == 0:
            continue
        if visited & (1 << i):
            continue

        dp[now][visited] = min(dp[now][visited], dfs(i, visited | (1 << i)) + graph[now][i])

    return dp[now][visited]


graph = [list(map(int, input().split())) for _ in range(n)]

print(dfs(0, 1))