BOJ 2098: 외판원 순회

오늘의 문제는 well-known 알고리즘 중 하나인 TSP (Traveling Salesman Problem)을 이용한 문제인 외판원 순회 문제이다. 친구가 이 문제를 풀다가 어렵다고 해서 풀어봤었는데, 정말 이해하는데 오래 걸렸다. 사실 이 문제의 중요한 부분은 바로 비트마스킹인데, 아직까지 비트 연산을 이용해서 알고리즘을 풀어본 적이 많지 않아서 더욱 낯설었다.

우선, TSP라는 문제 자체가 아직도 최선의 해결책이 발견되지 않은 연구 중인 알고리즘이지만, 이 근간은 dynamic programming에 있다. 나도 이를 이용하여 해결했다.

import sys
input=sys.stdin.readline
n=int(input())
w=[list(map(int,input().split())) for _ in range(n)]
dp=[[0]*(1<<n)  for _ in range(n) ]
total=(1<<n)-1
def tsp(curr,visited):
    if visited==total:
        if w[curr][0]==0:
            return 1e10
        else:
            return w[curr][0]
    if dp[curr][visited]!=0:
        return dp[curr][visited]
    dp[curr][visited]=1e10
    for i in range(1,n):
        if not visited &(1<<i) and w[curr][i]!=0:
            dp[curr][visited]=min(dp[curr][visited], tsp(i,visited|1<<i)+w[curr][i])
    return dp[curr][visited]
print(tsp(0,1))

우선, w는 각 지점까지의 거리를 나타낸다.

dp는 길들 사이의 최솟값을 저장하며, 새로운 최솟값이 생기면 최신화시켜주는 dp table이다.

 

여기서 total은 '가능한 모든 방문의 수'라고 할 수 있다. 예를 들면, 1,3,4번 지점을 들렸다고 하자. (어떤 방식으로든) 그러면 1101 (이진수) 로 이를 저장한다. 만약 모든 곳을 다 방문했다면, 1111(2)로 나타낼 수 있다. 이는 결국 2의 4승 -1, 즉 15와 값이 같다. 

 

tsp 함수를 설명하겠다.

curr는 현재 현재 방문중인 노드를 의미한다.

그리고 visited는 아직까지 방문한 노드가 비트마스킹으로 표현되어있다.

재귀적으로 돌면서, 아직 방문하지 않은 노드면 방문하여 최솟값을 비교한다. 

 

if visited==total 이라는 것은, 모든 노드를 방문했다는 뜻이다. 

if dp[curr][visited] !=0 라는 것은, 중간에 한 번 방문되었던 좌표라는 뜻이다. 다시 확인할 이유가 없다.

 

여기서 for 문을 이용해서 움직일 수 있는 점들을 확인해보는데,

visited & (1<<i)라 함은, 다음 갈 지점이 아직 방문하지 않은 곳임을 확인할 수 있다.

예시로,

앞서 1011를 예시로 들면,

1을 2비트만큼 옮기면 100이다.

1011과 100의 and는 0000이기때문에, 방문하지 않았음을 확인할 수 있다.

그리고 w[curr][i]을 통해 아직 이 노드를 방문하지 않았음을 보장한다.

이를 통해 dp의 값을 새로 바꿀 수 있다. 

여기서 흥미로운 표현법은 바로 

tsp(i, visited|1<<i)인데, i는 다음 이동할 지점이고, 1<<i를 통해 다음 이동한 지점까지 포함시킨다.

즉, 1011 예시에서 0100이 and 연산이 되면, 

다음 이동할 좌표가 2에, 1111이 visited의 값에 들어갈 것이다.