[Baekjoon] 우주 탐사선(python)

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

문제 접근

이 문제는 플로이드 워셜 + 순열로 해결해야 하는 문제이다.

 

출발하는 행성에서 모든 행성을 탐사하는데 걸리는 시간을 구해야 하므로, 최단경로를 구할 때 출발 행성에서 다른 행성까지의 최단경로를 구하는 다익스트라나 밸만포드보다는 모든 행성 간 최단경로를 구할 수 있는 플로이드 워셜 알고리즘을 이용해야 한다.

 

모든 행성 간 최단경로를 구했으면 방문하는 순서를 결정해야 한다.

 

permutations 함수를 통해 출발 행성을 제외한 나머지 행성들의 순열을 구하고 거리의 합이 가장 작은 경우를 구해주면 된다.

---

풀이 과정

1. 플로이드 워셜을 통한 모든 정점 간 최단경로 계산

for k in range(N):
    for i in range(N):
        for j in range(N):
            if i == j:
                continue

            if graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

 

2. 출발 행성을 제외한 나머지 행성들의 순열 구하기

range 함수를 통해 순열을 구할 리스트를 만들고 출발 노드의 번호를 삭제한 뒤 permutations 함수를 통해 순열을 구한다.

numbers = list(range(N))
del numbers[K]

permus = list(permutations(numbers))

 

3. 구한 순열대로 행성 간 거리를 합산하여 최솟값 구하기

위에서 구한 순열대로 각 행성 간 거리를 합산하여 가장 작은 값을 구해주면 된다.

for order in permus:
    start = K
    dist = 0

    for i in order:
        dist += graph[start][i]
        start = i

    result = min(result, dist)

---

정답 코드

"""
    백준 17182번 우주 탐사선
"""
import sys
from itertools import permutations

N, K = list(map(int, sys.stdin.readline().split()))
graph = []

for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().split())))

for k in range(N):
    for i in range(N):
        for j in range(N):
            if i == j:
                continue

            if graph[i][j] > graph[i][k] + graph[k][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

numbers = list(range(N))
del numbers[K]

permus = list(permutations(numbers))

result = sys.maxsize

for order in permus:
    start = K
    dist = 0

    for i in order:
        dist += graph[start][i]
        start = i

    result = min(result, dist)

print(result)