정글사관학교 27일차 TIL: 외판원 순회 문제(TSP) -1

제목에서 번호가 1이라고 적혀있는 건 두 가지 이유가 있다. 1) 당연히 두 번째 포스팅이 있을 예정이라는 뜻이며, 2) 굳이 하나 더 쓰는 이유는 지금 이 글을 쓰는 나는 아직 이 풀이를 온전히 이해하지 못했기 때문이다..(내일의 내게 넘긴다)

 

저번 8일차 글에서 외판원 순회 문제를 DP로 푸는 풀이를 정리한 적이 있었다. 결국 이 문제는 순열로 푸는 풀이로 해결할 수 있었는데, 그 이유는 이 문제가 정확히는 외판원 순회 2로, 보다 낮은 난이도(더 넉넉한 시간과 넉넉한 메모리)였기 때문이다. 하지만 찐 외판원 순회 문제에서는 순열 따위 1도 먹히지 않는다. 1초라는 시간 제한과 128MB라는 메모리 제한으로 DP 이외에는 답이 풀리지 않는다.

 

오늘 내일 작성할 외판원 순회 관련 풀이는 이 블로그 내용을 많이 참조했는데, 저번에 봤던 장황한 풀이보다 훨씬 깔끔하게 내용을 전달해주고 있다. 다만 비트 마스크 등에 관한 내용은 빠르게 넘어가는데 이 부분은 내 예전 글을 참조하거나 저 블로그의 이전 글을 보면 보다 쉽게 이해가 가능할 것이다. 여기서도 부가적으로 설명을 덧붙일 예정.

 

저 글에서 말하는 중요한 인사이트 3가지를 여기서도 언급해본다. 순서는 약간 바꿔봄.

 

 

먼저, 이 풀이에서는 find_path라는 함수를 설계해 시작점에서 중간 지점까지의 최소 비용을 구한다. find_path에는 최종적으로는 두 가지 변수만 들어가는데, 시작은 네 가지 변수에서 출발해 왜 두 변수가 빠지게 되는지를 아래에서 설명할 것이다. 일단 필요한 것은 아래 네 가지이다.

 

1. start: 시작 도시

2. last: 현 지점(중간 경로)에서 마지막으로 방문한 도시

3. V: 이제까지 방문한 도시 집합

4. tmp_dist: 중간 경로의 길이

 

이 중, 1, 4는 나중에 필요없게 되고 최종적으로는 last와 V만 사용해서 중간 경로까지 갔을 때에 대한 최소 비용을 반환하게 한다. 그럼 아래 중요한 세 가지 인사이트에 대해 설명한다.

1. 시작 도시는 중요하지 않다.

저번 풀이에서도 설명했지만, 일단 외판원 순회 문제에서는 start를 고정시켜도 된다. 어디서 출발하건 정답에 해당하는 경로가 반드시 포함되기 때문. (저번 글을 참조하면 이해가 쉽다.) 따라서 외판원 순회를 풀 때 시작 도시는 중요하지 않다. 우리는 0번 도시로 이를 고정하겠다.

따라서 마지막 도시만 생각해주면 된다. 이게 어떤 경로가 될 거냐면

 

1(시작도시) -> 2-> ...-> 5(마지막 도시) -> 1 (찐 마지막 도시인데 이건 굳이 신경 쓸 필요 X: 시작도시와 찐 마지막 도시는 1로 고정되기 때문)

저번 풀이에서는 출발 도시 다음 출발 도시를 신경쓰고 나머지 도시를 A라는 집합에 넣어서 생각했는데(위에서는 2번 도시가 해당) 이 풀이에서는 마지막 도시를 중심으로 생각한다는 차이가 있다.

 

2. 구체적인 경로는 중요하지 않다.

이 블로그 풀이에서도 방문 도시에 대한 집합을 비트 마스킹으로 표현한다. 그런데 저번 풀이와 거의 반대 개념이라고 생각이 드는 게, 저번에는 아직 방문하지 않은 도시를 집합 A에 넣었다고 하면 이번에는 지금까지 방문한 도시를 집합 V에 넣는 식. 대신 이번 풀이에서는 저번 풀이에서 P라고 하는, 다음 경로를 반환하는 방식으로 쓰는 게 아니라 find_path에서 중간까지의 경로 중 마지막 지점인 last를 함수 내에서 반환하는 식으로 이어진다.

 

쉽게 말해, 방문하는 지점을 집합에 계속 넣고 마지막 방문 지점에 대해서만 last로 임시 저장해두는 식. 

 

3.  중복 확인

마지막으로, 특정 start, last, V에서 이들을 활용한 find_path(start, last, V)가 실제 중복 호출되는지 확인해야 한다. DP에서 핵심은 sub-P가 중복 호출되어야 기존에 저장해놨던 값으로부터 빠르게 불러온다는(Memoization)점이기 때문. 중복 호출이 안되는지 확인하는 게 아니라 중복이 일어나는지를 확인하는 것이다! 헷갈리면 안됨!

 

예시를 보자. 도시의 개수가 10개 (N=10)이라고 할 때,

find_path(1, 2, {1, 3, 2}): 1에서 출발해 중간에 도시 3을 거쳐 2까지 왔을 때의 최소 비용

find_path(1, 3, {1, 2, 3}): 1에서 출발해 중간에 도시 3을 거쳐 3까지 왔을 때의 최소 비용

 

이 호출된다고 해보자. 우리는 최종적으로 모든 도시를 다 돌고 다시 1로 와야하니 두 함수는 이후에 find_path(1, 4, {1, 2, 3, 4})를 호출하게 될 것이다. 즉, 중복이 발생한다는 말이다. 게다가, 앞에서 우리는 경로가 중요하지 않다고 했다. 즉, 위의 예시에서 {1, 3, 2}나 {1,2,3}이나 상관없다는 말이다. 방문을 했냐 안했냐만 생각한다. 어차피 길이 있으면 경로 비용에 집어넣고 그 중 min을 이용해 최소 비용만 취할 것이기 때문.

 

여기에서 우리가 이해해야 하는 개념은 "특정 start, last, V에 대해 아직 방문하지 않은 모든 도시 각각을 방문하는 재귀함수를 호출하고 이 중 최솟값을 취한다"이다. 그래서 경로가 필요하지 않다는 것이다. 어차피 다 찍어볼 것이고 그 중 중복된 경로가 있다면 그걸 가져온 다음 최종적으로 min값만 도출하면 되니까.

 

여기까지 왔다면, 코드를 보면서 다시 이해해보자.

 

def tsp(dists):
    N = len(dists)
    VISITED_ALL = (1 << N) - 1
    cache = [[None] * (1 << N) for _ in range(N)]
    INF = float('inf')
    
    def find_path(last, visited):
        if visited == VISITED_ALL:
            return dists[last][0] or INF

        if cache[last][visited] is not None:
            return cache[last][visited]
            
        tmp = INF        
        for city in range(N):
            if visited & (1 << city) == 0 and dists[last][city] != 0:
                tmp = min(tmp,
		 	  find_path(city, visited | (1 << city)) + dists[last][city])
        cache[last][visited] = tmp
        return tmp
                
    return find_path(0, 1 << 0)

from sys import stdin

input = stdin.readline

N = int(input())
dis = []
for _ in range(N):
    a = list(map(int, input().split()))
    dis.append(a)

print(tsp(dis))

 

저 블로그에서와 마찬가지로 주요 내용을 코드와 함께 설명해보자.

 

 

cache = [[None] * (1 << N) for _ in range(N)]

캐시는 dp 테이블의 역할을 한다. 위에서 캐시를 초기화한다. 캐시의 행 개수는 도시의 개수와 같고 1<<N으로 방문한 도시 집합 V에 대응하도록 한다. 즉, 백준 문제 기준으로 4 X 16 (N = 4니까 도시가 0번 도시, 1번 도시, 2번 도시, 3번 도시 총 4개이니 이진수에서 각 자릿수와 도시 개수를 대응시키면 총 2**4니까 16)만큼의 dp 테이블이 형셩된다. 현재는 None값이지만 나중에 계산하면 캐시에는 visited (비트 마스크로 표현한 방문 도시 집합)를 거쳐 마지막 방문 도시 last까지 오는 데에 대한 비용을 저장하게 된다.

 

if visited == VISITED_ALL:
    return dists[last][0] or INF

만약 모든 곳을 싹다 방문했다면 dists에는 최종 도착지인 0번 도시를 제외하고 마지막 방문 도시인 last에서 0까지 가는 비용이 저장되어 있을 것이니 이것을 반환하거나, 중간에 경로가 끊어져 있다면 INF를 반환할 것이다.

 

if cache[last][visited] is not None:
    return cache[last][visited]

맨 처음에 우리는 캐시를 초기화했는데, 캐시에 값이 저장되어 있고 우리가 dist를 계산하는 과정에서 만약 이미 해당 거리 비용을 계산하고 캐시에 미리 저장해뒀다면 그걸 불러오면 된다.

 

tmp = INF        
for city in range(N):
    if visited & (1 << city) == 0 and dists[last][city] != 0:
	tmp = min(
		  tmp,
		  find_path(city, visited | (1 << city)) + dists[last][city]
		  )

cache[last][visited] = tmp

tmp는 재귀함수를 돌릴 때마다 그때그때 최소비용을 임시로 저장해두는 변수로, 시작할 때는 무한대로 저장해놓는다. 이후 for문을 돌면서 visited와 city 사이에 교집합이 없다면, 즉 이미 방문한 도시 집합에 for문 돌아서 나온 city가 존재하지 않다면 우리는 거기를 다음 도착지로 생각할 여지가 있다. 그러려면 현 시점에서 마지막 위치인 last와 다음에 갈 위치 city 사이에 경로가 있어야 하니 그 값이 0이 아니라면

 

tmp는 find_path(city를 다음 경로의 마지막 위치로 하고, visited와 city의 합집합(즉, city를 visited에 넣는다)에 대한 비용을 계산) + 여기다가  

 

그 다음에는 캐시를 업데이트.

 

--오늘은 여기까지--