[Python] 백준 - 2098 외판원 순회

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

 
 

필요한 도구

 
 
1. 비트마스크 : 
 
1) bit & (1 << i) :
 
(1 << i)는 1의 $2^{i}$이고, AND 연산은 bit와 (1 << i) 둘 다 1이거나 0 일 때, 1을 출력한다.
방문여부를 체크할 때 사용된다.
 
2) bit | (1 << i) :
 
(1 << i)는 1의 $2^{i}$이고, OR 연산으로 bit와 (1 << i) 둘 중 하나가 1이면, 1을 출력한다.
방문여부를 저장할 때 사용된다.
 
3) bit == (1 << n) - 1 : n = 4일 때, 01111이다. 모두 방문했을 경우다.
 
2. dp = [[ 끄고켜는 비트배열 ] * n(노드수)]
3. dfs탐색알고리즘
 
 
 

문제해결방법

 
 
아래 문제와 비슷하지만, 1311번 문제는 사람마다 순차적으로 남아있는 할 일을 배당받는 개념이라 dfs(idx, bit)로 재귀함수를 호출하는 부분에 dfs(idx+1, bit|(1 << i))로 진행된다.
 
이 문제는 노드가 연결되어 있으면(주어진 W[i][j]가 0이 아니면), 모두 방문할 수 있는 토대에서, 최소길이 루트를 찾는 것이다. (dfs함수의 첫번째 인자는 for문을 돌고 있는 다음 노드가 전부 해당된다.)
 

[Python] 백준 - 1311 할 일 정하기 1

 
 
1. dfs함수에서 다음 호출되는 dfs함수의 값을 변수(res)에 저장하고, return값을 지정한다는 것은 dfs가 끝까지 호출된 후, 값을 상향식으로 반영하여 추려지는 조건이 있으면 그 조건대로 통과하고, 첫 출발점에 종합한 값을 저장할 수 있다는 것이다.(토너먼트)
 
2. 첫 출발점으로 돌아올 수 있어야 한다고 하였기에, n = 4일 때, bit가 01111(십진수15)이 되는 시점의 노드는 start노드로 향하는 길이값이 있어야만 한다. start노드로 향하는 값이 있다는 말은 싸이클이 있다는 거다. 노드끼리 사이클이 있을 경우, start는 어떤 노드부터 해도 같다. (총 길이값은 같기 때문.)
 

- 코드

import sys
input = sys.stdin.readline

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

def dfs(node, bit):
    if bit == (1 << n)-1:
        if lth[node][0]:
            return lth[node][0]
        else:
            return INF
    if dp[node][bit] != -1:
        return dp[node][bit]
    ans = INF
    for next in range(n):
        if bit & (1 << next) == 0 and lth[node][next] != 0:
            res = dfs(next, bit|(1 << next))
            ans = min(ans, res + lth[node][next])
    dp[node][bit] = ans
    return ans

print(dfs(0, 1))