# 문제
외판원 순회 문제는 영어로 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의 범위가 다르다.
모든 경우를 전부 탐색하는 완전 탐색으로 풀이할 경우 시간 복잡도는 가 되어
최악의 경우, 16!인 20922789888000만큼 연산을 하게 되어 시간 초과가 난다.
이를 해결하기 위해서 비트마스킹과 DP를 활용해 시간복잡도를 로 줄일 수 있다.
이 문제를 풀기 위해서는 도시를 방문하는 경로의 모든 경우의 수를 찾아야 하기 때문에, 방문한 도시와 방문하지 않은 도시를 계속해서 추적해야 한다.
방문한 도시에 대한 정보를 배열을 사용해서 저장하게 되면, 도시의 수가 많아질수록 메모리를 굉장히 많이 차지하게 된다.
배열 대신에 비트마스킹을 사용하면 단일 정수를 사용해서 방문한 도시 집합을 나타낼 수 있다.
각 비트는 도시를 의미하고 그에 대한 값으로 방문 여부를 나타낸다.
예를 들어, 5개의 도시가 있는 경우 {1, 3, 4} 도시를 방문했다면 이진법으로 로 나타낼 수 있다.
이렇게 비트마스킹을 사용하게 되면 공간 복잡성을 크게 줄일 수 있고,
연산 또한 배열을 사용하는 것보다 훨씬 빠르게 수행할 수 있어 시간 복잡도를 개선할 수 있다.
이 문제에 비트마스킹을 적용하기 위해서 필요한 것들을 먼저 알아보자!
1(2) | 100(2) == 101(2)
visited | (1 << next) # next: 현재 방문할 도시
1(2) & 100(2) == 0
visited & (1 << next) # next: 현재 방문할 도시
visited == (1 << N) - 1 # N: 도시의 개수
0번째 도시를 방문처리 한 후 탐색을 시작한다.
👉 같은 경로를 거치게 된다면, 해당 경로 안에서는 어떤 도시에서 출발하든 같은 비용을 갖기 때문에 0번째 도시로 출발 도시를 고정해도 됨.
비트마스킹을 활용해 0번째 도시 방문을 표시한 visited를 함수에 전달한다.
visited: 1(2)
dp = {}
def DFS(now, visited):
~~~
print(DFS(0, 1)) # now: 0번째 도시부터 방문, visited: 0번째 도시 방문 처리
모든 도시를 방문한 경우, visited의 값은 이 된다.
💡 도시가 4개인 경우, 모두 방문하면 이 될 것이고, 은 인 15에 해당한다.
다시 출발 도시로 돌아가는 비용을 리턴한다.
이때 출발 도시로 돌아갈 수 없는 경로라면, 무한대를 반환해 이 경로가 최소 비용으로 채택되지 않게 한다.
(여기서 리턴된 값이 이 경로의 비용에 더해진다.)
# 모든 도시를 방문한 경우
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까지 방문한 최소 비용
continue
continue
min_cost = int(1e9)
for next in range(1, N):
# 비용이 0이어서 갈 수 없거나, 이미 방문한 루트면 무시
if world[now][next] == 0 or visited & (1 << next):
continue
도시에 방문하면 해당 도시에 해당하는 비트의 값을 0에서 1로 바꿔준다.
or 연산(|) : 왼쪽과 오른쪽 중에서 하나라도 1인 비트의 값이 모두 1이 된다.
현재 도시를 방문하는 비용과 DFS를 통해 모든 도시를 방문하는데까지 드는 비용을 합친 합을 cost
에 담고,
최저 비용인지 확인해 min_cost
를 갱신한다.
cost = DFS(next, visited | (1 << next)) + world[now][next]
min_cost = min(cost, min_cost)
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번째 도시 방문 처리