[백준 파이썬] 17182번 우주 탐사선

최단 경로

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

문제
우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위치와 ana호가 행성 간 이동을 하는데 걸리는 시간이 2차원 행렬로 주어진다. 행성의 위치는 0부터 시작하여 0은 행렬에서 0번째 인덱스에 해당하는 행성을 의미한다. 2차원 행렬에서 i, j 번 요소는 i 번째 행성에서 j 번째 행성에 도달하는데 걸리는 시간을 나타낸다. i와 j가 같을 때는 항상 0이 주어진다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하여라.

탐사 후 다시 시작 행성으로 돌아올 필요는 없으며 이미 방문한 행성도 중복해서 갈 수 있다.

입력
- 첫 번째 줄에는 행성의 개수 N과 ana호가 발사되는 행성의 위치 K가 주어진다.
(2 ≤ N ≤ 10, 0 ≤ K < N)
- 다음 N 줄에 걸쳐 각 행성 간 이동 시간 $T_{ij}$ 가 N 개 씩 띄어쓰기로 구분되어 주어진다.
(0 ≤ $T_{ij}$ ≤ 1000)

출력
- 모든 행성을 탐사하기 위한 최소 시간을 출력한다.

입력예시1
3 0
0 30 1
1 0 29
28 1 0

출력예시1
2

입력예시2
4 1
0 83 38 7
15 0 30 83
67 99 0 44
14 46 81 0

출력예시2
74

sol) 플로이드-워셜 알고리즘 이용 (N 범위가 크지 않고, 방문한 행성 중복도 가능하므로 이를 사용하는 것이 유리)
점화식:   $D_{ij} = min(D_{ij},~~ D_{ik}+D_{kj})$

import sys

INF = int(1e9)  # 무한을 의미하는 값으로 10억을 설정

n, k = map(int, input().split())  # 행성 개수, 행성 위치 입력 받기
# 2차원 리스트 행성 간 이동시간 입력받기
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

visit = [False] * n
visit[k] = True
result = INF

# 점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1, n):
    for i in range(1, n):
        for j in range(1, n):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

def find_min(curr, count, cost):
    global result
    if count == n:
        result = min(result, cost)
        return
    for i in range(n):
        if not visit[i]:
            visit[i] = True
            find_min(i, cost + graph[curr][i], count + 1)
            visit[i] = False

find_min(k,1,0)
print(result)