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

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

17182번: 우주 탐사선

 

 

# 조건

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

 

# 접근 방법

• 플로이드 워셜을 이용하여 각 노드에서 다른 노드까지의 최단 거리를 구해준다.
• 따라서 각 노드에서 다른 노드로 가는 모든 edge는 최단 시간을 보장하고, 이 경로들 중에 최단 시간이 되는 값을 DFS로 탐색하면됨

-> depth는 N이고 중복 방문이 없기 때문에 각 부모 노드의 자식 노드는 (N-depth)개 가 된다.

import sys  
n, k = map(int,sys.stdin.readline().split())  
arr = [list(map(int,sys.stdin.readline().split())) for _ in range(n)]  
  
hist = [False if i == k else True for i in range(n) ]  
  
minval = [sys.maxsize]  
  
def DFS(r, c,time, depth):  
    if depth == n-1:  
        minval[0] = min(minval[0], time)  
        return  
  
    if time > minval[0] :  
        return  
  
    for j in range(n):  
        if j != c and hist[j]:  
            hist[j] = False  
            DFS(c, j, time + arr[c][j], depth+1)  
            hist[j] = True  
  
  
  
for tt in range(n):  
    for i in range(n):  
        for j in range(n):  
            if i == j : continue  
            arr[i][j] = min(arr[i][j], arr[i][tt] + arr[tt][j])  
  
for c in range(n):  
    if k != c and hist[c]:  
        hist[c] = False  
        DFS(k, c, arr[k][c],1)  
        hist[c] = True  
  
print(minval[0])