[백준] 2098번: 외판원 순회

문제

백준 - 2098번: 외판원 순회

분석

외판원 순회 문제(Traveling Salesman problem)는 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획한다고 할 때, 가장 적은 비용을 들이는 방법을 말한다.

모든 가능한 경로를 나열해서 구할 수도 있지만 시간 복잡도가 O(n!)이므로 n이 커질 수록 매우 오래걸린다.
이는 DP와 DFS, 비트마스킹을 이용하면 O(n^22^n) 으로 비교적 완화된 시간에 답을 구할 수 있다.

now가 현재 도시이고, visited가 지금까지 방문한 도시정보를 가진다고 할 때,
dp[now][visited] = (남은 도시들을 최적으로 돌았을 때 드는 최소 비용) 이다.

visited는 비트로 봤을 때 방문정보를 확인할 수 있다.
n이 4라고 할 때, 도시는 0, 1, 2, 3 이 있다.
0001은 0에 방문한 것이고, 0010은 1에, 0011은 0과 1모두 방문한 것으로 생각하면 된다.
따라서 어느 도시 x에 방문하고자 할 때 비트 or연산으로 다음과 같이 구할 수 있다.

visited |= (1 << x)

dp 점화식은 다음과 같이 세울 수 있다.
현재 도시를 now, 다음에 방문할 곳을 nxt라고 할 때
dp[now][visited] = min(dp[now][visited], dp[nxt][visited | (1 << nxt)]+W[now][nxt])
그런데 처음에 dp를 INF로 초기화하면 이렇게 했을 때 도달하지 못해서 INF 인 건지, dp가 계산이 안되어서 INF인건지 구분이 안된다. 따라서 -1로 초기화하고, mn값에 최소 비용을 저장해둔 후, 루프가 끝나면 dp[now][visited]에 mn을 넣는다.

이는 DFS 방식으로 재귀하면서 구한다.
만약 visited가 (1 << n) - 1이라면 모든 도시를 방문했다는 뜻이다.
ex) n = 4, 1 << 4 = 10000 -> -1하면 01111 이므로 0, 1, 2, 3에 모두 방문
따라서 출발 지점으로 돌아가기만 하면 된다. 이때 출발지로 돌아가는 방법이 있다면 W[now][0]값을 반환하고, 없다면 INF값을 반환한다.
그리고 dp[now][visited]가 -1이 아니라면 계산된 적 있는 값이므로 바로 값을 반환하여 중복 계산을 막는다.

그리고 아무 도시에서나 시작해도 최소 비용은 같다.
외판원 문제는 최소 비용이 드는 사이클을 찾는 것이기 때문에 그렇다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

n = int(input())
W = []
for _ in range(n):
    W.append(list(map(int, input().split())))
INF = sys.maxsize
dp = [[-1]*(1 << n) for _ in range(n)]

def TSP(now, visited):
    if visited == (1 << n)-1:
        if W[now][0]: return W[now][0]
        else: return INF
    if dp[now][visited] != -1:
        return dp[now][visited]
    mn = INF
    for nxt in range(1, n):
        if W[now][nxt] == 0 or visited & (1 << nxt):
            continue
        mn = min(mn, TSP(nxt, visited | (1 << nxt))+W[now][nxt])
    dp[now][visited] = mn
    return dp[now][visited]

print(TSP(0, 1))

끝으로..

새로운 개념인 외판원 순회에 대해 배워봤다.