BOJ - 17182 - 우주 탐사선

import sys

def DFS(arr, visit, ret, index, dist, planet, N):
    if ret[0] < dist: return
    if planet == N:
        ret[0] = min(ret[0], dist)
        return

    for i in range(N):
        if visit[i]: continue
        else:
            visit[i] = True
            DFS(arr, visit, ret, i, dist + arr[index][i], planet + 1, N)
            visit[i] = False

def solution():
    _INF = 1e9
    N, M = map(int, sys.stdin.readline().split())
    Floyd = []
    for _ in range(N):
        Floyd.append(list(map(int, sys.stdin.readline().split())))

    for k in range(N):
        for i in range(N):
            for j in range(N):
                if i == j: continue
                Floyd[i][j] = min(Floyd[i][j], Floyd[i][k] + Floyd[k][j])

    ret = [_INF]
    visit = [False] * N
    visit[M] = True
    DFS(Floyd, visit, ret, M, 0, 1, N)
    print(ret[0])

solution()

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