백준 / python / 2098. 외판원 순회

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

 

문제 요약

2~16(N)개의 도시가 주어질 때, 최소한의 비용으로 모든 도시를 순회할 때 발생하는 비용을 구하라.

 

 

풀이 요약

1. "순회" 를 하기 때문에 어느 지점에서 시작해도 상관이 없다. A 가 시작 도시라고 해보자.
2. A~E 의 도시를 방문하였고 F ~ Z 의 도시를 앞으로 방문해야하며 현재 도시는 E 라면, A~D 의 방문 순서가 어떤 순서였던지간에 상관없이, 항상 같은 비용(E에서 F~Z 를 방문하고 마지막에A 로 방문하는 최소 비용)을 추가해야할 것이다. 이 비용을 저장해서 dp 로 푸는 것이 핵심이다.
3. 방문했는지 여부를 N 개의 정수로 나타낼 수도 있겠지만 비트마스킹을 사용하여 한 개의 정수로 나타내면 메모리를 절약할 수 있다.
4. 그럼 dp[now][10011] 은 1, 2, 5 번 도시를 방문하였고 현재 now 번 도시에서 1, 2, 5 번 도시를 제외한 도시들을 거쳐 A 로 돌아가는 비용이다.

 

주의사항

1. 리스트가 딕셔너리보다 200ms 정도 빠르다.
2. min 을 안쓰면 300ms 빨라진다.

 

from sys import stdin, maxsize

input = stdin.readline

N = int(input())
costs = []
dp = [[0] * (1 << N) for _ in range(N)]
INF = maxsize

for _ in range(N):
    costs.append(list(map(int, input().split())))


def solve(now, index):
    if index == (1 << N) - 1:
        return costs[now][0] if costs[now][0] else INF

    if dp[now][index]:
        return dp[now][index]

    dp[now][index] = INF

    for i, value in enumerate(costs[now]):
        if value == 0:
            continue

        if index & (1 << i):
            continue

        temp = solve(i, index | (1 << i)) + value

        if dp[now][index] > temp:
            dp[now][index] = temp

    return dp[now][index]


print(solve(0, 1))