[BOJ] Q2098 외판원 순회

[BOJ] Q2098 외판원 순회

Question

Language: Python

Difficulty: Gold 1

해당 문제는 잘 알려진 TSP(Traveling Salesman Probelm) 문제이다.

모든 노드를 다 순회해야되는데, 이때의 비용을 최소로 하는 경로를 찾아야한다. 주어진 문제의 조건에 따라 완전 탐색을 수행하는 경우 16!의 경우의 수를 모두 비교해야하므로, 이는 시간 초과가 발생하게 된다. 따라서, 해당 문제는 dp를 이용해서 풀어야 한다.

dp

dp=[[-1] * (1<<n) for _ in range(n)]

위와 같은 배열을 이용해서 memoization을 수행한다. 위의 bitmasking 방식을 활용해서 특정 비트의 값이 1인 경우 이는 해당 노드를 방문했다는 의미이다.

예를 들어, 0001은 1번 노드를 방문했다는 뜻이다. 0011은 1,2 번 노드를 방문했다는 뜻이다.

특정 노드를 방문 했을때, 해당 노드에 대해 특정 노드 조합에 대한 거리를 저장하고 있으면, 해당 노드 경로에 대한 순회를 중복적으로 할 필요가 없다.

Solution

from math import inf
def solution():
    dp=[[-1] * (1<<n) for _ in range(n)]
    visited_all=(1<<n) -1
    #last는 마지막으로 간 도시(즉, 현재 있는 도시) visited는 현재까지 방문 노드의 정보를 비트로 표현한 것
    def dfs(last,visited):
        #모든 노드를 방문한 경우, 현재 노드에서 시작 노드까지의 경로가 있으면 거리를 반환하고, 없으면 무한대 반환
        if visited==visited_all:
            return distances[last][0] or inf
        #해당 노드 조합에 대한 방문 기록이 있는 경우
        if dp[last][visited]!=-1:
            return dp[last][visited]
        
        distance=inf
        #각각의 노드 조합에 대한 거리를 비교해서 최소가 되는 거리를 택한다.
        for city in range(n):
            if visited & (1<<city) == 0 and distances[last][city] !=0:
                distance=min(distance,distances[last][city]+dfs(city,visited|(1<<city)))
        dp[last][visited]=distance
        return distance

    print(dfs(0,1))

if __name__ == "__main__":
    n=0
    distances=[]
    result=inf

    with open("input2098.txt","r") as file:
        n=int(file.readline())
        distances=[list(map(int,file.readline().split())) for _ in range(n)]
    
    solution()