99클럽 코테 스터디 21일차 (BOJ 17182 우주탐사선)

오늘의 문제 : BOJ 17182(우주 탐사선)

문제 설명

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

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

 

문제풀이

주어진 문제는 모든 행성을 탐사하는 모든 경로의 최소값을 구해야 한다. 모든 경로를 구하는데는 비트마스킹을 최단 경로 구하기는 다익스트르라를 사용해서 풀이 하였다. 예를 들어 행성이 3개가 주어진다면 방문 표시를 비트마스킹을 사용하여 이진수 3자리로 사용 가능하다. 이 경우 경우의 수는 이진수로 000, 001, 010, 100, 011, 110, 101, 111 이 나오게 되며 1이 

행성을 방문한 경우 0이 방문하지 않은 경우 이다. 또한 최소값을 기록하기 위한 테이블도 생성하여 사용한다.

문제에서 주어진 시작 행성이 1이라면 방문 표시를 010 으로 시작한다. 이땐 dp[010][1] 은 0으로 비용을 초기화하고 나머지는 최대값을 설정한다. 1번 행성부터 0번 2번 행성을 방문하면서 최소비용을 구하는 로직을 다익스트르라를 사용해서 구한후 dp[111] 리스트의 최소값을 구해주면 된다. 여기서 dp[111][0] 0번 행성을 마지막으로 모두 방문한 경우, dp[111][1] 1번 행성을 마지막으로 모두 방문한 경우 dp[111][2]는 2번 행성을 마지막으로 모두 방문한 경우이다.

import sys
from heapq import heappop, heappush

n, k = map(int, input().split())

matrix = [list(map(int, input().split())) for _ in range(n)]

INF = float('inf')

# 경우의 수 비트마스킹
# 1000(2) = 8
max_state = (1<<n)


# 방문 경로에 따른 모든 최소비용 저장할 DP
dp = [[INF for _ in range(n)] for _ in range(max_state)]

# 출발지점의 최소 벼용 0으로 초기화
dp[1<<k][k] = 0

heap = []
heappush(heap, (0, 1<<k, k))

while heap:
    cost, state, j = heappop(heap)

    # j 행성에서 모든 행성 탐사
    for i in range(n):
        # i 번 행성 방문 표시
        next_state = (1<<i) | state
        # i번 행성까지 탐사완료 후 cost
        next_cost = cost + matrix[j][i]
        if dp[next_state][i] > next_cost:
            dp[next_state][i] = next_cost
            heappush(heap, (next_cost, next_state, i))

answer = min(dp[(1<<n)-1])

print(answer)