[백준 🥇3] 17182번 우주 탐사선 (Python/파이썬)

1️⃣ 문제

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

2️⃣ 코드

플로이드 + 백트래킹으로 풀었당

import sys

INF = sys.maxsize

n, k = map(int, input().split())
time = []
for _ in range(n):
    time.append(list(map(int, input().split())))

def floyd():
    dist = [[INF] * n for _ in range(n)]

    for i in range(n):
        for j in range(n):
            dist[i][j] = time[i][j]

    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][j] > dist[i][k] + dist[k][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist

# 모든 우주선을 탐사하는 각 경로에 대해 걸리는 시간 구하기 
def pick(s, visited, cnt, t):   
    if cnt == n:   # cnt는 탐색한 노드의 개수
        answer.append(t)
        return

    for i in range(n):
        if not visited[i]:
            visited[i] = True
            pick(i, visited, cnt+1, t+dist[s][i])
            visited[i] = False
        
    
dist = floyd()

visited = [False for _ in range(n)]
visited[k] = True

answer = []
pick(k, visited, 1, 0)
print(min(answer))