[백준 2098] 외판원 순회(TSP) - 비트필드를 이용한 DP (파이썬 Python)

외판원 순회

문제

외판원 순회 문제는 영어로 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로 가기 위한 비용을 나타낸다.

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

출력

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

예제 입력

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

예제 출력

35

 

---

비트마스킹?

이 문제에서는 도시를 방문하는 경로의 모든 경우의 수를 찾아야되는데, 찾는 과정에서 방문한 도시와 방문하지 않은 도시를 계속 고려하면서 탐색해야됩니다.

방문한 도시에 대한 정보를 집합(set)이나 리스트를 사용해서 구현할수 있는데, 도시의 수가 많아질수록, 탐색하면서 경우의 수 * 집합이 되어서 메모리를 굉장히 많이 차지하게 됩니다.

리스트 대신에 비트마스킹으로 집합을 구현하면 방문한 도시 집합을 '정수'로 나타낼 수 있습니다.

 

도시들의 번호	9	8	7	6	5	4	3	2	1	0
도시들 방문 여부 ( 0 1)	0	0	0	1	1	1	0	0	0	0

각 비트는 도시를 의미하고 그에 대한 값으로 방문 여부를 0과 1로 나타냅니다. (이진수라 0과 1로 밖에 표현 못하기도 합니다.)
예를 들어, 4개의 도시가 있는 경우 {1, 4} 도시를 방문했다면 이진법으로 1001로 나타낼 수 있습니다.

이렇게 비트마스킹을 사용하게 되면 공간 복잡성을 크게 줄일 수 있고,
연산 또한 배열을 사용하는 것보다 훨씬 빠르게 수행할 수 있어 시간 복잡도를 개선할 수 있다.

 

이 문제에선 dfs로 탐색을 하는데, 그때 항상 쓰는 visited 리스트를 비트마스킹으로 구현 할 예정입니다!

---

비트마스킹 구현하기

이런 비트필드를 이용해서 집합연산하는 등의 알고리즘을 비트마스킹이라고 합니다.

여러 집합 연산들이 많지만, 이 문제에서 필요한 연산만 설명하겠습니다.

 

예를들어 4까지 도시들을 체크하려면 필드의 크기는 4이 되어야하므로 아래와 같이 설정하면 됩니다.

S = 0b0000

---

원소 추가

S에 num을 추가한다면, S의 num번 비트만 1을 만들어주면 됩니다.

(1 << num)은 num번째를 1로 설정주는 것으로,1 * 2^num 라고 생각해주면 됩니다. 1이란 비트를 num번 왼쪽으로 옮기는 거죠(num번 2를 곱함)

OR 연산을 해주면  num번째 1이 기존과 합집합이 되므로, 이미 있으면 아무일도 안일어나고, 존재하지 않았다면 num번째자리에 필드가 1이 추가되게 됩니다.

S |= (1 << num)

---

원소 삭제

S에서 num을 제거한다면, S의 num번 비트를 0으로 만들어주면 됩니다.

~은 not연산자로 모든 비트를 반전시킵니다.

~(1 << num)는 num번 비트만 0으로 만들고 나머지는 1로 만들어 주므로, 이것을 and연산자로 해주면 num번째가 0으로 바뀝니다.

S &= ~(1 << num)

---

원소 확인

S에서 num이 있는지 확인하려면 num만을 갖는 비트필드를 1<<num으로 만들어 주고, and연산자를 통해서 0이랑 비교해주면 됩니다.

0이면 없는 것이고, 0이 아니면 num이 있는 것입니다.

S & (1 << num) != 0
S & (1 << num) == 0

---

전체집합

1000 - 1 = 999가 되듯이, 총길이가 10인 이진수를 0b1111111111로 만들고 싶으면 길이가 하나 더 긴 (1<<10)에 대해서 -1을하면, 자리수가 10으로 한칸 줄어드고 나머지 비트가 1로 반전됩니다.

이 문제에서는 1023이 되고, 총 필드의 인덱스는 0~1023으로 총 1024가지를 표현할 수 있습니다.

S = (1 << 10) - 1

---

구현

1. DFS를 활용해 탐색을 시작한다.

같은 경로를 거치게 된다면, 해당 경로 안에서는 어떤 도시에서 출발하든 같은 비용을 갖기 때문에 0번째 도시로 출발 도시를 고정해도 됩니다.

0번째 도시를 방문처리 한 후 탐색을 시작합니다.

1<<0번째도시 하면 어차피 2의 0승, 즉 1이 되므로 그냥 1을 넣었습니다.

 

dfs는 '앞으로'의 최종까지의 총 거리 입니다.

dp = {}

# 앞으로의 거리
def DFS(now, visited):

	~~~~~~~
    
print(DFS(0, 1))  # now: 0번째 도시부터 방문, visited: 0번째 도시 방문 처리

---

Dfs 탐색 부분

길이 있는지 확인하고, 이미 탐색했던 길인지 확인하고 cost = dfs(i, (visited | 1<<i)) + adjacent[now][i] 이라는 점화식을 이용해서 dp를 적용해줍니다.

# 탐색 시작 & 최소 시간 구하기
    min_cost = INF
    for i in range(n):
        if adjacent[now][i] == 0:
            continue
        if (1<<i) & visited == 0:
            min_cost = min(dfs(i, (visited | 1<<i)) + adjacent[now][i], min_cost)
    dp[(now, visited)] = min_cost

---

메모리제이션

재귀호출 할때 이미 구한 경로면 dp 테이블에서 꺼내서 씁니다. 딕셔너리로 구현 했습니다. (자바로 치면 해시맵)

# 이미 구한 구간이면 메모리제이션
    if (now, visited) in dp:
        return dp[(now, visited)]

---

dp 메모리제이션 기법 적용

현재 방문할 도시와 이전까지의 루트가 동일한 경로를 이미 계산했다면, 다시 계산하지 않고 dp 딕셔너리에서 현재 도시와 방문도시의 집합을 저장한 비트필드 이진수를 key로 검색해서 방문 합니다.

    # 이전에 계산된 경우 결과 반환
    if (now, visited) in dp:
        return dp[(now, visited)] # now까지 방문한 최소 비용

---

모든 도시 방문했을때

현재도시(now)에서부터 0번 도시로 원점으로 돌아가야되는데 길이 없으면 sys.maxsize를, 있으면 그 경로의 거리를 반환합니다.

if visited == bit_range - 1:
        if adjacent[now][0] != 0:
            return adjacent[now][0] # 어차피 출발점은 0임, 앞으로의 거리므로 마지막 거리
        else:
            return INF

---

최종 DFS코드

# 앞으로의 거리
def dfs(now, visited):
    # 전부 다 탐색을 끝났다면?
    if visited == bit_range - 1:
        if adjacent[now][0] != 0:
            return adjacent[now][0] # 어차피 출발점은 0임, 앞으로의 거리므로 마지막 거리
        else:
            return INF
    # 이미 구한 구간이면 메모리제이션
    if (now, visited) in dp:
        return dp[(now, visited)]
    # 탐색 시작 & 최소 시간 구하기
    min_cost = INF
    for i in range(n):
        if adjacent[now][i] == 0:
            continue
        if (1<<i) & visited == 0:
            min_cost = min(dfs(i, (visited | 1<<i)) + adjacent[now][i], min_cost)
    dp[(now, visited)] = min_cost
    return min_cost

---

전체 코드

# 비트필드를 이용한 다이나믹 프로그래밍 -> dp 테이블 말고 딕셔너리 사용
import sys
input = sys.stdin.readline
n = int(input())
INF = sys.maxsize
adjacent = [] # 인접행렬
for _ in range(n):
    adjacent.append(list(map(int, input().split())))
bit_range = 1 << n
dp = {}

# 앞으로의 거리
def dfs(now, visited):
    # 전부 다 탐색을 끝났다면?
    if visited == bit_range - 1:
        if adjacent[now][0] != 0:
            return adjacent[now][0] # 어차피 출발점은 0임, 앞으로의 거리므로 마지막 거리
        else:
            return INF
    # 이미 구한 구간이면 메모리제이션
    if (now, visited) in dp:
        return dp[(now, visited)]
    # 탐색 시작 & 최소 시간 구하기
    min_cost = INF
    for i in range(n):
        if adjacent[now][i] == 0:
            continue
        if (1<<i) & visited == 0:
            min_cost = min(dfs(i, (visited | 1<<i)) + adjacent[now][i], min_cost)
    dp[(now, visited)] = min_cost
    return min_cost
print(dfs(0, 1<<0))