[백준] 17182번 우주 탐사선

💡문제접근

• 플로이드-워셜 알고리즘으로 각각의 출발점에서 발사했을 때 각각의 도착점에 도착하는데 걸리는 시간을 갱신한다.
• 모든 행성을 탐사하는데 필요한 최소 시간을 구하기 위해 백트래킹을 이용한다.

💡코드(메모리 : 31256KB, 시간 : 476ms)

import sys
input = sys.stdin.readline

N, K = map(int, input().strip().split())
T = [list(map(int, input().strip().split())) for _ in range(N)]
visited = [False] * N
result = int(1e9)

for k in range(N):
    for a in range(N):
        for b in range(N):
            if T[a][b] > T[a][k] + T[k][b]:
                T[a][b] = T[a][k] + T[k][b]

# 현재 ana호가 발사되는 행성의 위치, 방문한 행성의 개수, 소요된 시간
def recursive(current, cnt, time):
    global result
    if cnt == N:
        result = min(result, time)
        return
    for i in range(N):
        if not visited[i]:
            visited[i] = True
            recursive(i, cnt+1, time+T[current][i])
            visited[i] = False

visited[K] = True
recursive(K, 1, 0)
print(result)

💡소요시간 : 37m