[BOJ 2098] 외판원 순회 (Python)
복습 요망!
풀이
문제는 쉽게 이해했다. (다만 구현을 못했을 뿐...) 굉장히 이해하는데 오래 걸린 문제이다. 이해하는데 무려 2일이 걸렸다. 그리고 풀이와 이해에 정말 도움이 되는 블로그가 있다. 무조건 해당 글을 보는 것을 강추한다. (설명이 너무 잘되어있다!)
이 문제는 TSP(Travelling Salesman Problem) 문제로 아직도 연구중에 있는 알고리즘이라고 한다. TSP 알고리즘은 조합 최적화(Combinatorial Optimization) 문제로 전산학에서 연구된 가장 유명한 문제 중 하나라고 한다. TSP 알고리즘이란 무엇일까?
TSP 알고리즘
도시의 개수와 각 도시 쌍 간의 거리들이 주어질 때, 모든 도시를 한 번씩 방문하고 여행을 시작한 원래 도시로 돌아올 수 있는 최단거리 경로를 구하는 알고리즘이라고 한다.
이 문제의 특징은 비트 연산, DFS, DP를 모두 활용해서 풀어야한다는 것이다. 해당 개념을 활용하지 않고 완전탐색으로 푸는 방법도 있다. 하지만, O(N!)의 시간 복잡도로 인해 시간 초과가 발생하여 틀리게된다. (N이 작으면 통과할 수도 있으나 문제에서 최대 N은 16으로 16!은 10조가 넘는다.)
그리고 문제의 포인트는 순회 경로(사이클)을 만들 수만 있다면 시작점은 중요하지 않다는 것이다! 즉, 0번 도시에서 시작하든 1, 2, 3번 도시에서 시작하든 정답 경로는 반드시 지나가게 되므로 결국 시작점을 단일 도시로 고정하여도 어쨌든 정답 경로를 지나치게 된다. 따라서 시작 도시를 추적하지 않아도 된다. 해당 개념을 어떻게 사용했는지 설명하고 코드로 넘어가도록 하겠다.
① 비트 연산은 방문 체크를 확인하기 위해 사용한다고 생각하면 쉽다. 즉, n번째 비트의 on/off 여부로 n번째 도시를 방문했는지의 여부를 표현해준다. 예시를 통해 이해해보자.
(Ex) 도시의 수 N이 4일 때, 현재 방문 비트가 1001(₂)라고 가정하자
--> 이는 0번 도시, 3번 도시는 방문하였고(O), 1번 도시, 2번 도시는 방문하지 않았다는(X) 표현이다.
추가로 비트 연산자 &(AND)와 |(OR)를 사용하여 비트 연산으로 도시의 방문 여부와 방문 처리를 표현해준다.
② DFS를 활용하여 가장 적은 비용의 순회 여행 경로를 탐색하고, 시간 복잡도를 줄이기위해 DP를 활용한다고 생각하면 된다. DP를 활용하면 이전에 계산했던 최소 비용의 순회 경로를 다시 계산하지 않게되어 시간 복잡도가 줄게된다. 기존의 O(N!)의 시간 복잡도를 O(N x 2^N)으로 줄일 수 있게 된다. (+ 위에서 언급했던 시작점이 중요하지 않다는 사실로 인해 재귀 함수의 매개변수 1개(시작 도시 매개변수)를 더 줄일 수 있고 이는 시간 복잡도를 줄이는데 영향을 준다.)
코드에서는 cache[][] 리스트가 DP를 활용한 리스트이다. cache[][]리스트의 index에는 탐색한 경로를 저장하고, value에는 탐색한 경로의 최단 거리를 저장하게 된다. 아래를 보며 이해해보자.
cache[N][visited]는N번 도시 -> visited에서 방문하지 않은 도시 -> 0번 도시(=도착 도시이다. (시작 도시X)) 의 최단 경로를
의미한다.
(온전히 본인의 생각입니다. 지적 환영입니다!)
다른 예시를 통해 이해해보자.
(Ex)
cache[3][11] = 15란?
현재 N은 3이고, visited는 11로 2진수로 표현하면 1011(₂)이다. visited의 1011(₂) 의미는 2번 도시만 방문하지 않았고 나머지 도시는 전부 방문했다는 의미이다.
즉, 3번 도시 -> 2번 도시 -> 0번 도시(=도착 도시이다. (시작 도시X)) 의 최단 경로가 15라는 의미이다.
예시를 하나만 더 보자.
(Ex2)
cache[0][1] = 35란?
현재 N은 0이고, visited는 1로 2진수로 표현하면 0001(₂)이다. visited의 0001(₂) 의미는 0번 도시만 방문하였고 나머지 1, 2, 3번 도시는 전부 방문하지 않았다는 의미이다.
여기서 어려울 수 있는데, 우리가 알 수 있는 사실은 N이 0으로 출발은 0번 도시이며 도착은 무조건 0번 도시라는 것을 알 수 있다. 즉, 0번 도시 -> (~어떤 경로인지 모른다~) -> 0번 도시(=도착 도시이다. (시작 도시X)) 의 최단 경로가 35라는 의미이다. 추가로 위 예제에서는 visited를 통해 2번 도시만 방문하지 않았다는 사실을 알 수 있어 경로를 정확히 알 수 있었다. 하지만, 해당 예제에서는 정확한 경로를 모른다.
맞는 말이다. 중간 경로가 정확히 어떤 경로인지는 모르지만, 순회 경로라는 사실은 알 수 있다.
즉, 0 -> [1->2->3] or [3->2->1] or [1->3->2] or ... -> 0 인데, 수많은 순회 경로 중에서 최단 경로가 35라는 의미이다.
이러한 방식으로 cache[][] 리스트를 갱신하면서 최소 비용의 순회 경로를 탐색하여 답을 도출하게 된다. 최종적으로 모든 순회 경로(시작 도시=출발 도시)의 경우의 수들 중 최솟값이 리턴되어 답을 구할 수 있게 된다!
코드
import sys
input = sys.stdin.readline
n = int(input())
cities = [list(map(int, input().split())) for _ in range(n)]
# (1 << N) - 1 ==> 'N개의 비트를 모두 켠다'와 같음
VISITED_ALL = (1 << n) - 1
# DP를 위한 캐시 초기화
# 도시의 개수(N)에 대응하고 (1 << N)을 통해 방문한 도시 집합(visited)에 대응
# cache[N][visited] : N번 -> visited에서 방문 X한 도시 -> 0번 도시(시작 도시) 경로 저장한다고 생각하면 쉬움
cache = [[None] * (1 << n) for _ in range(n)]
INF = float('inf')
idx = 1
def find_path(last, visited):
if visited == VISITED_ALL:
# 마지막 방문 도시 출발 - 0번째 (출발 도시) 사이에 경로가 존재하면
# 경로 값을 반환.
# 경로가 존재하지 않는다면 무한값을 반환해서 답이 안되게 한다.
return cities[last][0] or INF # 마지막 도착 도시에서 출발 도시인 0으로 가야됨.(문제 조건)
# cache 값이 None이 아니라는 것은 last와 visited의 계산이 이미 수행됬고,
# 지금은 중복호출 되었다는 뜻임 -> 다시 계산하지 않고 값만 바로 반환하도록
# 중복계산을 없애 효율성 높임 --> DP 사용하는 이유
if cache[last][visited] is not None:
return cache[last][visited]
tmp = INF
for city in range(n):
if visited & (1 << city) == 0 and cities[last][city] != 0:
tmp = min(tmp, find_path(city, visited | (1 << city)) + cities[last][city])
cache[last][visited] = tmp
return tmp
print(find_path(0, 1 << 0))