[Python] 백준 17182 우주 탐사선

1. 문제 링크

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

17182번: 우주 탐사선

---

2. 문제 요약

모든 행성을 탐사하기 위한 최소 시간을 출력한다.

 

---

3. 아이디어 정리

1. 플로이드 와샬. 모든 정점 최단 거리 구하기
2. 행성을 백트래킹으로 탐색하여 모든 행성 방문하여 최소 시간 구하기

참고 - 플로이드와샬

모든 노드에서 다른 모든 노드까지의 최단 경로를 모두 계산한다. - 특정 노드를 거쳐 가는 경우 사용

플로이드 워셜 점화식

각 단계마다 특정한 노드 k를 거쳐 가는 경우를 확인한다.

• a에서 b로 가는 최단 거리, a에서 k를 거쳐 b로 가는 거리 비교

---

4. 문제 풀이

4-1. 내 풀이

import sys

def recursive(pos, cnt, cost):
    global result

    if cnt == N:
        result = min(result, cost)
        return

    for next in range(N):
        if not visit[next]:
            visit[next] = True
            recursive(next, cnt + 1, cost + graph[pos][next])
            visit[next] = False

N, K = map(int, sys.stdin.readline().split())
graph = [[*map(int, sys.stdin.readline().split())] for _ in range(N)]

# 1. 플로이드 와샬. 모든 정점 최단 거리 구하기
for k in range(N):
    for i in range(N):
        for j in range(N):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

visit = [False] * N
result = int(1e9)
visit[K] = True

# 2. 행성을 백트래킹으로 탐색하여 모든 행성 방문하여 최소 시간 구하기
recursive(K, 1, 0)
print(result)

 

---

5. 결론

• 플로이드 와샬을 이용해서 모든 정점과 최소값을 구한 뒤, 모든 행성을 방문하는 문제