[Baekjoon] 2098. 외판원 순회 [G1]

📚 문제

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

📖 풀이

TSP는 굉장히 유명한 문제이다. 해밀턴 경로를 구하는 문제로 쉽게 해결할 수 있는 알고리즘을 아직도 발견하지 못해 완전탐색만 가능하다. 따라서 N이 작은 경우만 해결이 가능하다.

중복없는 순열은 시간복잡도가 O(n!)인데 현재 가지치기를 할수 없고 완전탐색으로 모든 경우의 수를 구해줘야한다. 따라서 시간복잡도가 O(n!)이니 16!는 시간초과가 발생한다.

비트마스킹 DP의 시간복잡도는 O((n ^ 2) * (2 ^ n))으로 n이 16일 때 가능하다.

🧐 비트 마스킹 DP로 해결하는 방법

1. DP의 방문표시할 개수를 1 << n 만큼으로 만들어 준다. (여기서는 이전에 방문했던 값마다 바뀌니 2차원으로 만든다.)

   DP를 표현할 때 이전 값일 때의 visited를 다 다르게 만들어줘야 한다.

   예를 들면, 도시가 4개면 방문표시를 [0, 0, 0, 0]으로 한다고 하자. 방문할 때는 1로 바꾼다.

   현재 방문한 곳이 [1, 1, 1, 0] 인데, 이전에 방문한 곳이 1일 때와 2일 때 다르게 처리해줘야 한다.

   따라서 dp를 2차원으로 만들어준다. 그리고 bit로 나타내 방문표시를 다 만들어준다.

   n이 4이면 bit가 0000 ~ 1111까지 만들어줘야하는 것이다.

   따라서 dp = [[-1] * n for _ in range(1 << n)]로 방문표시를 해준다.

2. 방문표시를 bit로 표시하니 리스트가 아닌 정수로 만든다.

   정수이니 재귀함수의 인자로 데리고 다닌다. 다음 방문 bit를 확인할 때 visited & (1 << i)로 방문했는지 확인한다.

   방문하지 않고, 다음 움직일 값이 0이 아니면 움직일 수 있으니 이 때 다음 bit를 방문표시해준다. 방문표시는 visited | (1 << i)로 한다.

3. 마지막 다 방문했는지는 bit로 확인한다.

   visited가 1111..111(2)이 되면 다 방문한 것이기 때문에 (1 << n) - 1인지 확인하면 된다.

📒 코드

def recur(prv, visited):
    global ans
    if visited + 1 == 1 << n:           # 다 방문했는지 확인
        return arr[prv][0] or INF   # 도착점까지 이동한 값을 반환(갈 수 없다면 INF 반환)

    if dp[visited][prv] != -1:          # 반복계산을 줄이기 위한 메모이제이션 활용
        return dp[visited][prv]

    ret = INF
    for i in range(1, n):           # 첫번째 비트는 출발점으로 확인할 필요가 없다. 나머지 비트 확인
        if arr[prv][i] == 0 or visited & (1 << i):  # 갈수 없는지, 방문했던 비트인지 확인한다.
            continue
        # 최소값을 리턴, 다음 방문하기 위해 bit를 방문지점에 더해준다.
        ret = min(ret, arr[prv][i] + recur(i, visited | (1 << i)))
    dp[visited][prv] = ret          # 메모이제이션에 값을 넣어준다.
    return ret


n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
dp = [[-1] * n for _ in range(1 << n)]  # 최소값을 담아 줄 메모이제이션
INF = n * 1000000
print(recur(0, 1))

🔍 결과