[백준] 2098번 외판원 순회 (Python)

 

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

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

 

입력

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

 

DFS 코드

import sys

INF = 1e+9
n = int(input())
mat = []
for i in range(n):
    mat.append(list(map(int, sys.stdin.readline().split())))
    
dp = [[None for _ in range(1<<n)] for _ in range(n)]    #모든 방문 가능 경우의 수
chk = 1

def search(node, chk):
    if chk==(1<<n)-1:
        if mat[node][0]!=0:
            return mat[node][0]
        else:
            return INF

    if dp[node][chk]!=None: 
        return dp[node][chk]

    min_value = INF
    for i in range(1, n):
        if (mat[node][i]!= 0) and ((chk & (1<<i))==0):    #연결되어 있으며 방문한적 없을때
            min_value = min(min_value, search(i, chk | (1<<i)) + mat[node][i])
    dp[node][chk] = min_value

    return min_value


answer = search(0,chk)
print(answer)

처음에는 순열을 이용해 풀었는데 N이 최대 16이 될 수 있으므로 당연히 시간초과로 통과하지 못했다. 이후에도 여러 시도를 거친 뒤 결국은 대다수의 풀이가 DFS+DP로 구현되어 있어 그러한 코드를 다수 참고하여 구현하였다.

DP table

dp = [[None for _ in range(1<<n)] for _ in range(n)]    #모든 방문 가능 경우의 수

먼저 dp 테이블을 [각 노드] *[방문 가능 경로]의 크기로 지정했는데 dp 테이블을 하나만 지정하면 방문에 대한 체크가 어렵기 때문이다. (ex1->3->2, 1->2->3)

 

여기서 dp를 기존 dp 테이블과 같이 INF가 아니라 None로 지정했는데 이는 진행 중 모든 경로를 진행한 경우와 도달이 불가능한 경우를 나눠주기 위함이다. 만약 INF로 초기화하고 구현하면 무조건 시간초과가 뜬다.

 

백준의 예제에서는 이 케이스가 없어 확인하기 어려운데 조금 극단적인 입력을 넣어 반복수를 확인해보았다.

[INPUT]

10
0 1 1 1 1 1 1 1 1 1
1 0 1 1 1 1 1 1 1 1
0 1 0 1 1 1 1 1 1 1
0 1 1 0 1 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1
0 1 1 1 1 0 1 1 1 1
0 1 1 1 1 1 0 1 1 1
0 1 1 1 1 1 1 0 1 1
0 1 1 1 1 1 1 1 0 1
0 1 1 1 1 1 1 1 1 0

 

왼쪽: dp를 None으로 초기화했을때. 오른쪽: INF로 초기화 했을때

    if dp[node][chk]!=INF: 
        return dp[node][chk]

INF로 초기화하면 INF와 비교하며 방문을 체크하는데 순회가 불가능한 경로 또한 INF로 체크했으므로 이러한 경로 역시  통과하고 이후 쓸데없는 반복을 계속하기 때문이다.

 

BFS 코드

import sys
from collections import deque

INF = 1e+9
n = int(input())
mat = []
for i in range(n):
    mat.append(list(map(int, sys.stdin.readline().split())))
    
dp = [[INF for _ in range(1<<n)] for _ in range(n)]    #모든 방문 가능 경우의 수
chk = 1


dp[0][chk]=0
queue = deque([[0, chk]])
answer = [INF for _ in range(n)]
while queue:
    node, chk = queue.popleft()
    if chk==(1<<n)-1:
        if mat[node][0]!=0:
            answer[node] = dp[node][chk] + mat[node][0]
        else:
            dp[node][chk] = INF
    else:
        for i in range(1, n):
            if (mat[node][i]!= 0)and ((chk & (1<<i))==0):    #연결되어 있으며 방문한적 없을때
                if dp[node][chk] + mat[node][i] < dp[i][chk | (1<<i)]:
                    dp[i][chk | (1<<i)] = dp[node][chk] + mat[node][i]
                    queue.append([i, chk | (1<<i)])

answer = min(answer)
print(answer)

DFS를 구현하고 나면 BFS 역시 조금만 바꾸면 구현할 수 있는데 결과를 보면 BFS의 반복수가 DFS에 비해 적다. BFS는 위치와 경로 정보를 시작점부터 채워나가므로 반복이 겹치는 경우가 많기 때문이다. ex(1->2->3->4 이후 1->3->2->4)를 했을때 더 작은 경로만 큐에 넣어주면 된다.