[Python] 백준 2098 외판원 순원

 

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

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

 

 

 

 

 

난이도

골드 1

 

 

 

 

 

코드 

import sys
sys.setrecursionlimit(10**6)

def DFS(city, visit) :

    if dp[city][visit] != -1 :
        return dp[city][visit]

    if visit == 2**N-1 :
        if W[city][1] > 0 :
            return W[city][1]
        else :
            return float('inf')

    min_cost = float('inf')
    for i in range(2,N+1) :
        # 비트자리가 0인 것들에만 보냄
        tmp = 1 << (i-1)
        if visit & tmp == 0 and W[city][i] > 0:
            min_cost = min(min_cost,DFS(i,visit|tmp)+W[city][i])

    if min_cost != float('inf') :
        dp[city][visit] = min_cost
    else :
        dp[city][visit] = float('inf')
    return dp[city][visit]


N = int(sys.stdin.readline())
W = [[0]]
for _ in range(N) :
    w = [0] + list(map(int,sys.stdin.readline().split()))
    W.append(w)

dp = [[-1 for _ in range(1<<N)] for _ in range(N+1)]

print(DFS(1,1))

 

 

 

 

 

 

풀이

 

코드 흐름

1. DFS(1,1)로 1번 도시에서 출발하여 모든 도시를 방문하는 최소 비용을 찾는다.
2. 각 도시는 비트마스크를 이용해서 방문 여부를 관리하고 DP 테이블에 중복된 계산을 방지하기 위해 최소 비용을 저장한다.
3. 모든 도시를 방문하면 출발점으로 돌아가는 비용을 더하여 최소 비용을 계산한다.
4. 경로가 없으면 inf 값으로 반환하여 경로가 없음을 처리한다.

 

 

 

def DFS(city, visit):
    # 이미 계산된 값이 있는 경우 바로 반환
    if dp[city][visit] != -1:
        return dp[city][visit]

 

dp[city][visit]은 현재 city에 있으며 특정 visit 상태에서의 최소 비용을 저장하는 테이블.

값이 -1이 아니라면 이미 해당 경로에 대한 최소 비용이 계산된 것이므로 이를 재사용한다.

 

 

    # 모든 도시를 방문한 경우
    if visit == (1 << N) - 1:
        if W[city][1] > 0:
            return W[city][1]
        else:
            return float('inf')

모든 도시를 방문한 경우 시작 도시로 돌아갈 수 있는지 확인한다.

만약 갈 수 있는 경로가 없으면 inf를 반환한다.

 

 

min_cost = float('inf')
for i in range(2, N + 1):
    tmp = 1 << (i - 1)
    # 아직 방문하지 않은 도시로 이동
    if (visit & tmp) == 0 and W[city][i] > 0:
        min_cost = min(min_cost, DFS(i, visit | tmp) + W[city][i])

 

2번 도시부터 N번 도시까지의 모든 도시를 탐색(1번 도시는 출발점)

아직 방문하지 않았고, i번 도시로 가는 경로가 존재하는지 확인

존재하면 DFS 재귀 호출하여 i번 도시를 방문한 상태에서 최소 비용을 구하고 현재 경로 비용을 더해서 min_cost 값을 업데이트한다.