2098. 외판원 순회 문제 링크
문제 풀이 코드 링크
하...
도저히 설명없이는 풀 수 없었던 문제... 구글링을 열심히 했다. 시간 제한이 되게 빡빡해서, 생각조차 못한 부분을 수정해야했다.
문제 요약
일반적인 외판원 순회(Traveling Salesman problem) 문제이다.
1번부터 N번까지의 도시가 있고, 각 도시 사이를 이동하는 비용이 있다. 이때 모든 도시를 한번씩 순회하고 출발 도시로 돌아오는 경로의 최소 비용을 출력하는 문제이다.
입력은 도시의 크기 N이 주어진 후, N*N의 행렬로 각 도시 사이를 이동하는 비용이 주어진다. [i][j]에는 i에서 j로 이동하는 데에 필요한 비용이 저장된다. 이 값이 0일 경우 이동할 수 없다.
설명
우선 문제의 조건은 어느 한 정점에서 출발해 모든 정점을 한번씩 순회하고, 출발한 정점으로 다시 돌아오는 것이다. 결국 어느 정점에서 출발한다고 해도 비용은 똑같기 때문에, 무조건 0번째 정점에서 출발한다고 가정하고 풀이한다.
매 단계마다 고려해야할 정보는 2가지이다. 하나는 현재 방문중인 정점(다음에 이동할 정점까지의 비용을 계산해야하기 때문), 하나는 현재까지 방문했었던 정점들의 기록이다.
비트마스킹을 이용한 방문 정보 저장
정점들의 방문 정보를 간단하게 저장하기 위해 비트마스킹을 이용한다.
8개의 도시에 대해 방문 정보를 저장한다고 할 때, 8개의 비트를 사용하는 방식. 방문하지 않은 곳은 0, 방문한 곳은 1로 나타내면 해당 비트들을 하나의 정수로 나타낼 수 있다.
DP 배열 설계
고려해야할 정보가 2개이기 때문에 DP 배열 또한 2차원 배열로 생성한다.
dp[현재 방문중인 정점 V][방문한 정점들의 정보 C]이 때, C에는 위에서 비트마스킹으로 생성한 정수가 들어간다. 이때, dp 배열에 저장되는 값이 조금 헷갈릴 수 있는데, V에서 출발해, C에 대해 현재 방문하지 않은 정점들을 순회하는 데에 필요한 최소 비용이 저장된다.
만일dp[3][0b00001001]이라면, 3에서 시작해 0, 3을 제외한 모든 정점을 방문하는 데에 필요한, 즉 1, 2, 4, 5, 6, 7을 순회하는 데에 필요한 최소 비용을 저장한다.
Bottom-Up? Top-Down?
그동안 DP 문제는 주로 Bottom-Up 방식으로 풀었었는데, 이번에는 Top-Down 방식으로 풀 수 밖에 없었다.
dp 배열에 저장되는 값을 C에서 방문한 정점들을 순회하는 데에 필요한 최소 비용이라고 하고(이 경우 위의 예시에서는 0, 3을 순회하는 데에 필요한 비용을 저장한다), Bottom-Up 방식으로 풀이한다고 하면, dp[0][0b0001] 다음에 갱신해야하는 인덱스는 dp[1][0b0011], dp[2][0b0101], dp[3][0b1001]이다. 작은 단위부터 값이 순서대로 갱신되어야하는데 단순히 반복문을 이용한 순회만으로는 차례대로 순회할 수 없기 때문에, Queue를 이용해 (V, C)쌍을 저장해주어야한다.
그리고... 이렇게 풀면 메모리 초과가 발생한다.
Queue에 들어가는 요소는 도시 수의 제곱수로 증가하기 때문에...
따라서, 재귀를 이용한 Top-Down 방식으로 접근하였다.
각 단계에서의 갱신
갱신에 필요한 코드를 먼저 정리를 해 보자면, 아래와 같다.
dp[V][C] = min(dp[V][C], cost[V][W] + dp[W][C + (1 << W)])
여기서 W는 C에서 방문하지 않았던 정점 중 하나이다. 1 << W는 SHIFT 연산으로, W만큼 비트를 왼쪽으로 옮겨준다. 즉, 1 << W는 비트마스킹에서 W가 3이라면 1000이 되는 셈. 이렇게 앞서말한 비트마스킹 방식으로 현재 방문한 도시의 정보를 저장할 수 있다.
V에서 W를 거쳐 C에서 방문하지 않은 모든 정점들을 순회하는 데에 필요한 최소 비용은, V에서 W로 이동하는 데에 드는 비용 cost[V][W]에, W에서 출발해 C + (1 << W)에서 방문하지 않은 모든 정점들을 순회하는 데에 필요한 최소 비용을 더한 것과 같다. 이것을 표현한 것이 위의 코드.
저 코드만으로는 부족하다. dp[V][C]를 만족하기 위해서는 W에 대해서만 위의 코드를 진행하는 것이 아니라, 현재까지 방문하지 않은 모든 도시들에 대해 연산을 수행하고 나온 최소값을 저장해야한다. 이를 반복하면 결국 dp[V][C]를 완성할 수 있다.
그런데 가만보면 같은 내용을 필요로하는 부분이 몇 있다.
일단 재귀를 이용해 dp[V][C]를 한 번 계산하고 나면, 해당 내용은 다시 계산할 필요가 없다. 이를 dp 배열에 저장하고, 만일 추후 해당 내용을 필요로 한다면 다시 한 번 연산할 필요없이 그대로 해당 내용을 반환해주면 된다.
구현
입력 받기 & 함수 호출
N = int(input())
INF = 1e9
width = 1 << N
END = (1 << N) - 1
cost = []
for i in range(N) :
cost.append(list(map(int, input().split(" "))))
dp = [[-1] * width for i in range(N)]
answer = TSP(0, 1)
print(answer)dp 배열의 초기화 부분에서, 원래 -1이 아니라 INF로 초기화를 해주었다. 그랬더니, 메모리초과도 아니고 시간초과 발생. 초기화 과정이 생각보다 오래 걸리는 걸까... 따라서 dp 배열 갱신할 때마다 해당 인덱스에 대해서만 INF로 초기화를 진행해주었다.
END는 모든 비트에 대하여 1인 수로, 종료 조건을 검사할 떄 사용한다.
# cur부터 시작해 END까지 도달하는 데까지 필요한 비용을 반환.
def TSP(cur, visit) :
# 이미 계산한 값이라면 그대로 반환.
if dp[cur][visit] != -1 :
return dp[cur][visit]
# 모든 정점을 방문하였다면, 출발 정점(0)을 방문하고 종료.
if visit == END :
if cost[cur][0] != 0 :
return cost[cur][0]
else : # 현재 정점에서 0으로 이동하는 방법이 존재하지 않음.
return INF
# 초기화
dp[cur][visit] = INF
# 현재 정점에서 모든 정점으로 이동
for i in range(1, N) :
# cur -> i의 경로가 없음
if cost[cur][i] == 0 :
continue
# i를 이미 방문함
if visit & (1 << i):
continue
# 재귀 호출
dp[cur][visit] = min(dp[cur][visit], cost[cur][i] + TSP(i, visit | 1 << i))
return dp[cur][visit] # 최소 비용