https://www.acmicpc.net/problem/2098
시간 1초, 메모리 128MB

input :

• N (2 ≤ N ≤ 16)
• W[i][j] (1 <= W[i][j] <= 1000000)

output :

• 첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

조건 :

• 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획

• 단, 한 번 갔던 도시로는 다시 갈 수 없다.

---

TSP 알고리즘 1 : 문제 소개 및 완전탐색 구현 by Parkito
TSP 알고리즘 2: 동적 계획법 구현 by Parkito

위의 글에서 설명이 매우 잘 되어 있다. 저장을 하기 위해서 마지막에 도착한 지점과 현재까지 도착했던 지점들을 비트마스킹으로 저장한다.

파이썬에서 비트마스킹으로 저장을 할 경우 AND, OR 연산을 통해서 얻을 수 있는 값(숫자 값, 이진수가 아님)은 이 위치가 1, 0인지가 아니라 그 위치의 값을 반환한다. 이 점을 주의하자.

이 것을 완전탐색을 사용한다면 당연히 시간이 터진다. 그렇기에 dp를 통해서 반복되는 계산을 줄여주자.

DP

저장해야 하는 것.
dp[마지막 도시][현재까지 방문한 도시들]로 인덱스가 나타낸다.
방문한 도시들은 비트로 나타내기 때문에 이 열의 크기가 (1 << n)의 크기여야 한다.

기저사례

모든 도시를 방문

그런 경우 이 지점에서 출발 지점까지의 길이 존재하는 지 확인해야 한다.
출발 지점은 0으로 고정을 할 거니까 data 배열에서 확인만 해주면 된다.

DP의 이용

이미 계산해둔 값이 있다면 이 것을 리턴한다.
그렇지 않은 경우에는 새롭게 계산해 준다.

재귀 연산

확인을 할 때 주의를 해야 한다. AND연산을 통해서 0이 아닌지. 비어 있는지 확인해야 한다.
이 때의 리턴 값이 현재까지 존재하던 값과 비교해서 최솟값을 저장하도록 한다.

재귀를 수행할 때 현재 도시에서 다음 도시로 이동하는데 소요 되는 길이 값 + 추가적인 재귀를 수행 한 값과 비교.

그리고 이 값을 dp에 저장한다.

import sys

def tsp(last, visited):
    if visited == ALL_VISITED:
        return data[last][0] or float('inf')

    if dp[last][visited] != -1:
        return dp[last][visited]

    temp = float('inf')
    # 모든 도시를 확인 하는데 안에서 조건으로 걸러낸다.
    for next_city in range(n):
        # 비트 마스크로 출입을 확인하기 때문에 만약 도시가 0, 1, 2, 3인 것을
        # AND연산을 통해서 확인한다. -> 비트가 켜져있는지를 말하지 않고 그 비트의 값을 주기 떄문에
        # 1을 이용하려 하면 안 된다.
        if visited & (1 << next_city) == 0 and data[last][next_city] != 0:
            # OR연산으로 함수의 인자로 넘겨주기 때문에 현재 가지고 있는 visited는 변경이 생기지 않는다.
            temp = min(temp, tsp(next_city, visited | (1 << next_city)) + data[last][next_city])

    dp[last][visited] = temp
    return temp

n = int(sys.stdin.readline())
data = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [[-1] * (1 << n) for _ in range(n)]
ALL_VISITED = (1 << n) - 1

print(tsp(0, 1 << 0))