[백준 2098번] 외판원 순회 - python

문제 링크

https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

 

풀이 - 다른 블로그 참고 

TSP 알고리즘 

- 모든 도시를 한번씩 방문하고 여행을 시작한 원래 도시로 돌아올 수 있는 최단 거리를 구하는 알고리즘 

- 비트 마스킹, dfs, dp 를 활용하여 푸는 문제 

- 완전 탐색으로 풀 경우 시간 복잡도 O(N!)으로 시간초과 발생 

 

- 출발지로 다시 돌아오므로 사이클이 형성되기 때문에 시작점은 어디든 상관없다. 

- 비트 마스킹을 통해 방문 체크를 해준다. 

- DFS를 통해 가장 적은 비용의 경로를 탐색한다.

- DP를 통해 시간 복잡도를 줄인다. DP를 활용하면 이전에 계산했던 경로를 다시 계산하지 않아도 된다. 

  visited[i][j] 는 i번 도시에서 visited에 표시된 도시들을 방문하지 않고 시작도시로 왔을 때의 최단 경로 

import sys

input = sys.stdin.readline 

n = int(input())

graph = []

for _ in range(n):
    graph.append(list(map(int,input().split())))
    
# n개의 비트를 모두 켠다는 의미 
VISITED_ALL = (1<<n)-1 
# n번 -> visited에서 방문하지 않은 도시 -> 0번 도시(시작도시) 경로 
cache = [[None] * (1<<n) for _ in range(n)]
INF = float('inf')
index = 1 

def find_path(last, visited):
	# 모든 경로를 다 돌았을 때 -> 즉 출발 위치를 0으로 정했으므로 현재 위치에서 0 으로 갈 때 
    if visited == VISITED_ALL :
    	# 경로가 존재하면 경로 리턴, 아니면 INF
        return graph[last][0] or INF
    
    # 이미 수행되었다는 뜻 
    if cache[last][visited] is not None:
        return cache[last][visited]
        
    tmp = INF
    for c in range(n):
    	# 다음 도시로 가능 비용이 존재하고, 해당 도시를 방문하지 않았으면 
        if visited & (1<<c) == 0 and graph[last][c] != 0:
        	# 최솟값 갱신 
            tmp = min(tmp, find_path(c, visited | (1<<c)) + graph[last][c])
    
    cache[last][visited] = tmp
    return tmp

# 임의의 출발 도시 0에서 시작 
print(find_path(0, 1<<0))

- 꼭 다시 풀기