(Python/파이썬) - 백준(BOJ) 17182번 : 우주 탐사선

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

17182번: 우주 탐사선

---

• 문제 : 

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

 

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

 

 

 

---

• 풀이 :

플로이드-와샬 알고리즘을 사용하여 해결할 수 있는 문제입니다. 

 

플로이드-와샬 알고리즘은 그래프에서 최단 겅로를 구하는 알고리즘이며 O(N^3)으로 모든점에서 다른 모든 점으로 가는 최단 경로를 구할 수 있습니다. 

 

풀이입니다.

 

1. 문제에서 주어진 행성들간 이동 시간을 플로이드-와샬 알고리즘에 사용하여 모든 경로에 대한 최단거리를 기록합니다.

 

2. 시작점을 K로 하여 백트래킹을 실시합니다. 백트래킹은 K를 시작점으로 하는 모든 경로를 탐색합니다.

 

3. N개의 행성을 모두 탐색한 경우 해당 경로의 가중치와 현재까지 탐색한 경로의 가중치를 비교하여 최솟값으로 갱신합니다.

 

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline


N,K = map(int,input().split())
time = [list(map(int,input().split())) for _ in range(N)]
visited = [0 for _ in range(N)]
visited[K] = 1
answer = float("inf")
for k in range(N):
    for i in range(N):
        for j in range(N):
            time[i][j] = min(time[i][j], time[i][k] + time[k][j])

def find_min(curr, cost, cnt):
    global answer
    if N == cnt:
        answer = min(answer, cost)
        return
    for i in range(N):
        if visited[i] == 0:
            visited[i] = 1
            find_min(i, cost + time[curr][i], cnt+1)
            visited[i] = 0
find_min(K, 0, 1)
print(answer)