파이썬 백준 2098 외판원 순회

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
 
n = int(input())
W = []
for i in range(n) : 
    W.append(list(map(int, input().split())))
 
max = sys.maxsize
DP = [[max for i in range(1<<n)] for i in range(n)]
 
def DFS(start, now, gone) :
    if DP[now][gone] != max : 
        return DP[now][gone]     
    if gone == (1<<n) - 1 : 
        if W[now][start] != 0 : 
            DP[now][gone] = W[now][start]
            return DP[now][gone]
        else : 
            return max
    for next in range(n) : 
        if next != now and W[now][next] != 0 and not gone & 1<<next : 
            DP[now][gone] = min(DP[now][gone], DFS(start, next, gone | 1<<next) + W[now][next])
    return DP[now][gone]
 
print(DFS(0, 0, 1))

IDEA

아이디어 자체는 기존에 풀었던 10971 외판원 순회 2와 같다.

출발점, 현재점, 이미 갔던 곳, 누적 비용을 모두 함수의 변수로 들고 다니면서 DFS를 탐색하면 결과가 나온다.

하지만 재귀함수의 변수인 '이미 갔던 곳'은 길이 n의 리스트이다.

재귀함수가 실행되는 횟수 * n만큼의 메모리가 필요하고, 이는 n! * n의 메모리가 필요함을 의미한다.

10971에서 n=10일때는 그 값이 천만 단위에서 멈췄지만, 이 문제의 n=16에서는 요구하는 메모리가 300조이다.

 

이 메모리 부족을 해결하기 위해 길이 n의 리스트 대신 n자리 2진수 하나를 사용하며 이것이 비트마스킹이다.

n자리 2진수와 n으로 2차원 DP table을 기록할 경우 2^n * n의 메모리가 필요하다.

n=16일 때 이는 100만밖에 되지 않는다. 300조를 100만으로 줄이는 어마어마한 압축률이다.

그동안 메모리 부족으로 다른 방법을 고민했던건 다 부질없는 짓이었던거지...

 

line 10 ~ 11

최솟값을 찾아야 하므로 max로 채워진 2^n * n의 2차원 DP table을 만든다.

DP[now][gone]은 gone을 지나 현재 now에 있을때, 다 돌고 출발점까지 가는데 필요한 비용이다.

즉, 지금까지 누적된 비용이 아니라 앞으로 남은 비용을 의미한다. 이렇게 설정한 것은 아래의 DFS 때문이다.

gone은 간곳을 1, 안간곳을 0으로 표현한 n자리 2진수가 될 것이다.

 

line 13 ~ 25

DP table을 채워넣는 DFS를 설계한다.

먼저, degree가 0인 부분문제를 찾아 채워넣는다.

이 문제에서 degree가 0인 부분문제는 W[i][j]에 채워진 값들일 것이다.

모든 점을 다 돌았을 때 (gone = 11....11) DP[now][gone]은 now에서 start로 돌아가는 비용 W[now][start]이다.

즉, 임계 경로 문제를 풀 때처럼 도착점에 연결된 점들부터 역순으로 DP의 값이 결정된다.

굳이 '지금까지 누적된 비용'이 아니라 '앞으로 남은 비용'을 DP에 기록하는 것은 역순으로 채워나가기 때문이다.

 

정순으로 채워나가며 누적된 비용을 기록할 때의 점화식은 아래와 같았다.

f[now][gone] = min(f[before][gone-before] + W[before][now] for all before) 

그렇다면 역순으로 채워나가며 남은 비용을 기록할 때의 점화식은 아래와 같을 것이다.

f[now][gone] = min(f[next][gone+next] + W[now][next] for all next)

이를 코드로 구현하면 line 22 ~ 24가 된다.

시작점에서 DFS가 실행되면 아직 계산하지 않은 f[next][gone+next]를 요구하므로, 여기서 DFS가 재귀한다.

이를 반복하면 다 돌고 start(=end)에 돌아온 경우까지 도달할 것이고, 여기서부터 값이 채워지는 후위 순회가 된다.

 

line 27

모든 스타트점 i에 대해 DFS(i, i, 1<<i)를 실행하여 min을 구할 필요는 없다.

최소 경로가 모든 점을 돌아 스타트점으로 돌아오는 하나의 사이클이기 때문에, 어디서 실행하든 같은 경로가 결과로 나올 것이다. 아무 한 점에서 DFS를 실행하여 답을 출력한다.

 

 

memo (line 16)

1<<n이 2^n을 뜻하므로 당연히 비트연산자 <<는 사칙연산 덧뺄셈보다 우선권이 있다고 생각했다.

하지만 그렇지 않은가 보다. 비트연산자로 표현된 수를 덧뺄셈할 경우 덧뺄셈이 먼저 계산되므로  괄호를 쳐야한다.

1<<n - 1 != 2^n - 1

1<<n - 1 = 2^(n-1)

(1<<n) - 1 = 2^n -1