[99클럽/파이썬 챌린저/21일차] 우주 탐사선

백준 17182번 우주 탐사선 G3

 

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

입력
첫 번째 줄에는 행성의 개수 N과 ana호가 발사되는 행성의 위치 K가 주어진다. (2 ≤ N ≤ 10, 0 ≤ K < N) 다음 N 줄에 걸쳐 각 행성 간 이동 시간 Tij 가 N 개 씩 띄어쓰기로 구분되어 주어진다. (0 ≤ Tij  ≤ 1000)

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

 

 

그래프 이론, 브루트포스 알고리즘, 비트마스킹, 최단 경로, 백트래킹, 플로이드-워셜

 

중복 방문도 가능하며, 입력 가능한 행성의 수는 10 이하로 매우 작다.

플로이드-워셜을 통해 각 최단거리를 구했다.

그 후, 비트마스킹 + DP로 최종 결과를 구해냈다.

 

비트마스킹을 사용하는 부분은 외판원 순회랑 유사하다고 느꼈다

 

 

 

import sys

n, k = map(int, sys.stdin.readline().split())

w = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

dp = [[-1] * 1024 for _ in range(10)]

pos = [[k, 0b0000000000 | (1<<k)]]
dp[k][0b0000000000 | (1<<k)] = 0

for k in range(n):
    for i in range(n):
        for j in range(n):
            if i == j: continue
            w[i][j] = min(w[i][j], w[i][k] + w[k][j])

while pos:
    next_pos = []
    for v, visit in pos:
        val = dp[v][visit]
        for i in range(n):
            next_visit = visit | (1<<i)
            if dp[i][next_visit] == -1:
                next_pos.append((i, next_visit))
                dp[i][next_visit] = val + w[v][i]
            dp[i][next_visit] = min(dp[i][next_visit], val + w[v][i])
    pos = next_pos

total_visit = 0b0000000000
for i in range(n): total_visit = total_visit | (1<<i)

result = 1000000
for i in range(n):
    if dp[i][total_visit] == -1: continue
    result = min(result, dp[i][total_visit])

print(result)

 

 

---