acmicpc.net 2098(TSP), 10971(2098과 동일)

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

유명한 TSP문제. dp와 더불어 비트마스크도 써야 한다. 

문제에 안써있는데 1번 도시부터 출발해서 돌아오는 경우로 해야 한다.

1. 마을을 방문했다는 뜻의 visited변수는 정수 하나다.(리스트 아님.) visited변수의 비트를 이용해서 

방문했는지 표시를 한다.

ex) 

visited가 1이면 이진수로 1이므로 1번 도시를 방문했다.

visited가 3이면 이진수로 11이므로 1,2번 도시를 방문했다.

...

visited가 (2의n승)-1이면 이진수로 1111~~1111 이므로 1~n번까지 도시를 전부 방문했다라고 해석할수 있다. 

ex) n==4일경우 (2의4승-1)의 이진수는 1111이다. 이 경우 모든 도시(1,2,3,4번)를 방문했다.

2. dp테이블에는 다른도시'들'을 방문했고, i번째 도시로 갈 경우의 최소값이 적혀져있다. 2차원 리스트인데, 행은 갈 도시, 열은 갔다온 도시를 뜻한다.

dp[0][3] == dp[0][이진수 11] ==0,1번 도시를 갔다와서 0번 도시로 갈 경우의 최솟값.

dp[2][10] == dp[2][이진수1010] ==2,4번 도시를 갔다와서 2번 도시로 갈 경우의 최솟값.

dp행은 n의 최댓값인 16개까지 들어갈 수 있고, 열은 1111111111111111(1이 16개)가 다 들어갔을경우인 65536까지 생길수 있다.

이걸 기초로 dp로 짜준다.

# -*- encoding: cp949 -*-
INF = 999999999
def TSP(city, visited):
    global dp
    if visited == ((1<<n)-1):  #111~~1111인게 확인되면, 즉 모든 마을을 다 돌아봤으면
        if arr[city][0] != 0: #첫번째 마을로 돌아오는 길이 있으면
            return arr[city][0] # +돌아오는길
        return INF #첫번째마을로 돌아오는길이 없으면 그냥 무한대..
    ret = dp[city][visited]
    if ret != INF: return ret #가장 짧은 길이 있으면 계산 안하고 리턴

    for i in xrange(n): #모든 마을을 돌면서
        if (visited & (1<<i)) or arr[city][i]==0: continue #방문을 했거나 갈 길이 없으면 continue.
        ret = min(ret, TSP(i, visited | (1<<i)) + arr[city][i]) #dp테이블을 최소화시켜주기 위한 계산. 원래의 ret와 방문했을때의 값의 최솟값.
    dp[city][visited] = ret #dp테이블 갱신
    return ret

n = input()
arr = [map(int,raw_input().split())for i in xrange(n)] #입력받는부분
dp = [[INF for j in xrange(65536)]for i in xrange(16)] #위에서 말한 행이 16개, 열이 최대 65536개
print TSP(0,1) #첫번째인자 0은 첫번째 마을에서 시작, 두번째인자 1은 이진수로 1. 즉 첫번째마을을 방문했다는 소리.