BOJ - 10971 - 외판원 순회 2

import sys

INF = 1e9

def TPS(graph, dp, idx, path, N):

    total = (1 << N) - 1

    if path == total:
        return graph[idx][0] if graph[idx][0] > 0 else INF
    if dp[idx][path] > 0:
        return dp[idx][path]

    tmp = 1e9
    for i in range(1, N):
        if (path >> i) % 2 == 1 or graph[idx][i] == 0:
            continue
        tmp = min(tmp, graph[idx][i] + TPS(graph, dp, i, path|(1 << i), N))
    dp[idx][path] = tmp


    return tmp

def solution():
    N = int(input())
    graph = []
    dp = [[0] * (1 << N) for _ in range(N)]
    for _ in range(N):
        graph.append(list(map(int, sys.stdin.readline().split())))

    print(TPS(graph, dp, 0, 1, N))
solution()

https://www.acmicpc.net/problem/10971