[백준] 외판원 순회

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

2098번: 외판원 순회

다이나믹 프로그래밍과, bit masking을 이용하는 문제입니다.

 

우선 문제의 핵심부터 간단하게 요약하면,

N개의 도시를 임의의 도시에서 출발해서 한번씩 전부 방문하고 원래 있던 도시로 돌아오는 최소 비용을 구해야하는 문제입니다. 

 

https://en.wikipedia.org/wiki/Travelling_salesman_problem

Travelling salesman problem - Wikipedia

사실 이 문제는 위의 백준 문제 지문에서도 언급 되었듯이 전산학에서 TSP problem으로 잘 알려진 문제라고 합니다. 

 

<Solution>

우선 이 문제는 random한 도시에서 출발을 할 수 있습니다. 하지만 결국 그 도시로 돌아오는 cycle을 구성하므로 임의로 특정 도시에서 출발하는 최단 거리를 구하는 문제와 동일합니다. 이제 문제의 핵심 알고리즘에 대해 설명해 보겠습니다. 

 

문제의 핵심 알고리즘은 두가지입니다. 

1. Dynamic programming을 (이미 방문한 도시, 현재 위치한 도시)의 쌍으로 부터 남은 도시를 모두 돌아 출발 도시로 오는 최솟값을 저장하도록 합니다.
   즉 dp[현재 위치한 도시][기존에 방문한 도시] = k 와 같이 저장을 해둡니다. 그렇다면, 중복되는 계산을 줄일 수 있습니다. 
   1~6번 마을이 있다고 가정해봅시다. 1->2->3->4->5->6의 경로와 1->3->2->4->5->6의 경로에서 1~4번 마을을 거친 이후의 최단경로는 두 경로에서 똑같이 쓰일 수 있다는 것을 알 수 있습니다. 즉 위의 주황색으로 칠한 부분을 생각해보면, 현재 위치한 마을은 4로 동일하고, 이전에 방문했던 마을도 1,2,3으로 동일하기에 이후의 경로는 공통으로 사용할 수 있다는 것을 알 수 있습니다. 
2. 이전의 방문했었던 마을을 [1,2,3,4] 이런 형태로 저장하지 않고 bitmasking을 해서 integer number 1개로 저장합니다.
   위의 예시처럼 1,2,3,4 번 마을을 방문했다는 사실을 list로 저장하면, int 4개를 저장하는 만큼의 memory가 필요해서 매우 비효율적입니다. 이것을 _ _ _ _ 4개의 bit를 0,1로 마스킹해서 저장을 해둡니다. 0b1111 = 15 즉 15라는 숫자 하나가 1,2,3,4 마을을 방문했다는 사실을 represent할 수 있습니다. 더불어 and or 연산으로 쉽게 마을의 방문 여부 check 또한 가능합니다.

실제 구현은 TSP라는 함수를 재귀적으로 두어서 다이나믹 프로그래밍 중에서도 Top down 방식을 사용하였습니다. 

 

다이나믹 프로그래밍 문제를 푸는 방법은 Top down방식과 bottom up 방식이 있는데 이 문제의 경우 굳이 고려하지 않아야 하는 dp의 부분들이 많기 때문에 Top down이 더 적절한 것을 생각 할 수 있습니다. (피보나치 수열의 경우 물론 일반항이 존재하기는 하지만 점화식을 사용하게 구현하면, 이전항을 구하지 않으면 다음항을 구하지 못함) 

 

실제 구현은 아래와 같습니다. 

dp 테이블의 경우 아직 search 하지 않은 경우엔 -1, unreachable한 것이 밝혀 진 경우, int(2e9)로 간주하였습니다. 

실제 구현을 할 때 주의 해야하는점은 unreachable한 것을 알게 된 것도 기록을 해두어야 한다입니다.

import sys

N = int(sys.stdin.readline().rstrip())

graph = []

for _ in range(N):
    graph.append(list(map(int, sys.stdin.readline().rstrip().split())))

# for easy calculation assume node starts with 0 ~...
dp = [[-1] * (2**N) for _ in range(N)] # -1 if not searched yet

def TSP(current_node, bitmask): # bitmask-> nodes which are already visited
    if bitmask | (0b1 << current_node) == (0b1 << N) -1:
        # current node is last node
        if graph[current_node][0] != 0:
            return graph[current_node][0]
        else:
            return int(2e9)

    if dp[current_node][bitmask] != -1:
        return dp[current_node][bitmask]

    # else -> new -> should calculate
    ret = int(2e9)
    for i in range(N):
        if bitmask & (0b1 << i) or i == current_node or graph[current_node][i] == 0:
            continue
        tmp = TSP(i, bitmask | (0b1 << current_node))
        if tmp == int(2e9):
            continue
        if ret > graph[current_node][i] + tmp:
            ret = graph[current_node][i] + tmp
    
    dp[current_node][bitmask] = ret

    return ret

print(TSP(0, 0))