[python] 백준 2098 :: 외판원 순회 (DP, 비트마스킹)

[외판원 순회]

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

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

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

풀이

이 문제는 완전 똑같은 문제인 외판원 순회 2와 도시의 개수를 나타내는 N의 범위가 다르다.

• 외판원 순회 2: (2 $\leq$ N $\leq$ 10)
• 지금 문제: (2 $\leq$ N $\leq$ 16)

모든 경우를 전부 탐색하는 완전 탐색으로 풀이할 경우 시간 복잡도는 $O(N!)$가 되어
최악의 경우, 16!인 20922789888000만큼 연산을 하게 되어 시간 초과가 난다.

 

이를 해결하기 위해서 비트마스킹과 DP를 활용해 시간복잡도를 $O(N^2 * 2^N)$로 줄일 수 있다.

 

비트마스킹

0. 비트마스킹을 사용하는 이유🤔

이 문제를 풀기 위해서는 도시를 방문하는 경로의 모든 경우의 수를 찾아야 하기 때문에,

방문한 도시와 방문하지 않은 도시를 계속해서 추적해야 한다.

방문한 도시에 대한 정보를 배열을 사용해서 저장하게 되면, 도시의 수가 많아질수록 메모리를 굉장히 많이 차지하게 된다.

배열 대신에 비트마스킹을 사용하면 단일 정수를 사용해서 방문한 도시 집합을 나타낼 수 있다.

💡 How..?

각 비트는 도시를 의미하고 그에 대한 값으로 방문 여부를 나타낸다.

예를 들어, 5개의 도시가 있는 경우 {1, 3, 4} 도시를 방문했다면 이진법으로 $11010(2)$로 나타낼 수 있다.

 

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

 

이 문제에 비트마스킹을 적용하기 위해서 필요한 것들을 먼저 알아보자!

1. 시프트 연산

• 비트 시프트 연산을 이용해 비트를 왼쪽으로 이동시킬 수 있다.
• 왼쪽 시프트 연산을 하게 되면 이진수의 비트는 지정된 위치 수만큼 왼쪽으로 이동하고 빈 위치는 0으로 채워진다.
• 예를 들어 $1(2)$을 왼쪽으로 두 자리 이동하면 $100(2)$이 된다.

2. 방문한 도시로 추가하기

• 도시에 방문하면 그 도시에 해당하는 비트의 값을 0에서 1로 바꿔준다.
• or 연산(|) : 왼쪽과 오른쪽 중에서 하나라도 1인 비트의 값이 모두 1이 된다. 1(2) | 100(2) == 101(2)

visited | (1 << next) # next: 현재 방문할 도시

3. 방문했는지 확인하기

• and 연산(&) : 왼쪽과 오른쪽 중에서 겹치는 부분이 하나도 없는 경우, 0이 된다.
  👉 0을 반환하면 방문하지 않은 도시이다. 1(2) & 100(2) == 0

visited & (1 << next) # next: 현재 방문할 도시

4. 모든 도시에 방문했는지 확인하기

• 모든 도시에 방문한 경우 N만큼 1로 채워져있을 것이고, 그 값은 $(1 << N) -1$ 과 동일하다.
  💡 도시가 4개인 경우, 모두 방문하면 $1111(2)$이 될 것이고, $1111(2)$은 $2^4-1$인 15에 해당한다.

visited == (1 << N) - 1 # N: 도시의 개수

 

구현

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

• 0번째 도시를 방문처리 한 후 탐색을 시작한다.
  👉 같은 경로를 거치게 된다면, 해당 경로 안에서는 어떤 도시에서 출발하든 같은 비용을 갖기 때문에
  0번째 도시로 출발 도시를 고정해도 됨.
• 비트마스킹을 활용해 0번째 도시 방문을 표시한 visited를 함수에 전달한다.
  visited: 1(2)

dp = {}

def DFS(now, visited):

    ~~~

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

 

2. 모든 도시를 방문한 경우, 돌아가는 비용을 구한다.

• 모든 도시를 방문한 경우, visited의 값은 $(1 << N) - 1$이 된다.
  💡 도시가 4개인 경우, 모두 방문하면 $1111(2)$이 될 것이고, $1111(2)$은 $2^4-1$인 15에 해당한다.
• 다시 출발 도시로 돌아가는 비용을 리턴한다.
• 이때 출발 도시로 돌아갈 수 없는 경로라면, 무한대를 반환해 이 경로가 최소 비용으로 채택되지 않게 한다.
  (여기서 리턴된 값이 이 경로의 비용에 더해진다.)

    # 모든 도시를 방문한 경우
    if visited == (1 << N) - 1:
        # 다시 출발 도시로 갈 수 있는 경우 출발 도시까지의 비용 반환
        if world[now][0]:
            return world[now][0]
        else:
            # 갈 수 없는 경우 무한대 반환 (이 경로가 최소비용으로 채택되지 않게)
            return int(1e9)

 

3. 이전에 계산된 루트인 경우, dp를 활용한다.

• 현재 방문할 도시와 이전까지의 루트가 동일한 경로를 이미 계산했다면,
  다시 계산하지 않고 dp 테이블에서 해당 값을 가져온다.

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

 

4. 다음 도시가 방문할 수 없는 도시라면 무시한다.

• 비용이 0인 도시는 갈 수 없으므로 continue

• 이 도시를 이미 방문했을 경우도 continue

방문 여부 확인하기

• 방문 여부를 확인하기 위해서 and(&) 연산을 사용한다.
• and 연산(&) : 왼쪽과 오른쪽 중에서 겹치는 부분이 하나도 없는 경우, 0이 된다.
  👉 0을 반환하면 방문하지 않은 도시이다.

    min_cost = int(1e9)
    for next in range(1, N):
        # 비용이 0이어서 갈 수 없거나, 이미 방문한 루트면 무시
        if world[now][next] == 0 or visited & (1 << next):
            continue

 

5. 방문할 수 있는 도시라면, DFS 탐색을 이어나간다.

• 현재 방문할 도시와 그 도시를 방문했음을 표시한 visited를 담아서 DFS 함수를 호출한다.

방문 여부 체크하기

• 도시에 방문하면 해당 도시에 해당하는 비트의 값을 0에서 1로 바꿔준다.
• or 연산(|) : 왼쪽과 오른쪽 중에서 하나라도 1인 비트의 값이 모두 1이 된다.
• 현재 도시를 방문하는 비용과 DFS를 통해 모든 도시를 방문하는데까지 드는 비용을 합친 합을 cost에 담고,
  최저 비용인지 확인해 min_cost를 갱신한다.

        cost = DFS(next, visited | (1 << next)) + world[now][next]
        min_cost = min(cost, min_cost)

 

6. 현재 경로를 dp 테이블에 추가한다.

• 현재 도시까지 방문한 경우에서
  마지막 도시까지 방문을 마친 최소 비용을 구했으므로, 이 정보를 dp 테이블에 저장해둔다.

    dp[(now, visited)] = min_cost  # 현재 경우에서 최소 비용이 드는 루트의 비용 저장

 

끝!

전체 코드

import sys
N = int(input())
world = []
for _ in range(N):
    world.append(list(map(int, sys.stdin.readline().split())))

dp = {}


def DFS(now, visited):
    # 모든 도시를 방문한 경우
    if visited == (1 << N) - 1:
        # 다시 출발 도시로 갈 수 있는 경우 출발 도시까지의 비용 반환
        if world[now][0]:
            return world[now][0]
        else:
            # 갈 수 없는 경우 무한대 반환 (이 경로가 최소비용으로 채택되지 않게)
            return int(1e9)

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

    min_cost = int(1e9)
    for next in range(1, N):
        # 비용이 0이어서 갈 수 없거나, 이미 방문한 루트면 무시
        if world[now][next] == 0 or visited & (1 << next):
            continue
        cost = DFS(next, visited | (1 << next)) + world[now][next]
        min_cost = min(cost, min_cost)

    dp[(now, visited)] = min_cost  # 현재 경우에서 최소 비용이 드는 루트의 비용 저장
    return min_cost  # 비용 리턴


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