[Python 3] BOJ - 17182 "우주 탐사선"

 # 문제 링크

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

17182번: 우주 탐사선

 

 # 풀이

 개인적으로 이 문제의 핵심은 비트마스킹을 이용한 다이나믹 프로그래밍과 플로이드 와샬이라고 생각한다. 상태 공간을 현재 방문한 정점들의 비트인 bit, 현재 위치해있는 정점을 now라고 할 때 드는 최소비용인 dp[bit][now]라고 정의하자. 현재 문제에서 N의 제한이 10으로 매우 작기 때문에 상태 공간에 필요한 공간 복잡도는 $2^{10} * 10$이므로 매우 작기 때문에 메모리 제한이나 시간 제한에 걸리지 않고 여유롭게 정답을 구할 수 있다.

 그런데 현재 특정 정점 i에서 한번도 방문하지 않은 정점인 j를 갈 때는 반드시 i에서 j로 가는 비용이 최소임이 보장되어야 위에서 정의한 다이나믹 프로그래밍이 전체 문제에 대한 정답을 도출할 수 있다. 또한 상태공간에서 정의한 현재 정점인 now는 N개의 정점이 될 수 있으며, 갈 수 있는 정점또한 N개의 정점이 될 수 있으므로 모든 정점에 대한 최단거리가 필요하다. 이것을 위해서는 다이나믹 프로그래밍 이전에 플로이도 와샬로 각 정점 간의 최단 거리를 전처리해야 한다.

 

 # 코드

import sys

# go : 현재 방문한 정점의 비트가 bit, 현재 위치한 정점이 now일 때 걸리는 최소 비용을 리턴하는 함수
def go(bit, now):
    # Base Case : 모든 정점을 방문한 경우
    if bit == (1 << n) - 1:
        return 0
    # Memoization
    if dp[bit][now] != -1:
        return dp[bit][now]
    dp[bit][now] = 9876543210
    for idx, i in enumerate(arr[now]):
        # 현재 bit를 통해 방문되지 않은 정점이라면 방문
        if bit & (1 << idx) == 0:
            dp[bit][now] = min(dp[bit][now], go(bit | (1 << idx), idx) + i)
    return dp[bit][now]

# 입력부
n, m = map(int, sys.stdin.readline().split())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]

# 플로이드 와샬
for k in range(n):
    for i in range(n):
        for j in range(n):
            if arr[i][j] > arr[i][k] + arr[k][j]:
                arr[i][j] = arr[i][k] + arr[k][j]

# dp : 현재 방문한 정점의 비트가 bit, 현재 위치한 정점이 now일 때 최소비용을 저장하는 2차원 상태 공간 배열
dp = [[-1] * n for _ in range(1 << n)]
# 정답 출력
print(go(1 << m, m))