백준 2098번 : 외판원 순회 in Python

2098번: 외판원 순회

 

www.acmicpc.net

이 문제는 Traveling Salesman Problem(TSP)라 불리는, NP-complete 문제들 중 대표적인 문제로, 각 간선에 비용이 주어진 완전 그래프에서 모든 점을 한 번씩만 지나는 사이클 중 비용의 합의 최솟값을 구하는 문제이다.

위에서 말했듯이 이 문제는 NP-complete에 속해서 polynomial time 안에 해결하는 알고리즘이 알려진 게 없다. 그래서 입력의 크기가 작은 경우에만 적절한 시간 내에 해결이 가능하다.

이 문제는 이전의 할 일 정하기 1 문제처럼 DFS와 dynamic programming을 이용하면 상대적으로 효율적인 알고리즘을 만들 수 있다.

백준 1311번 : 할 일 정하기 1 in Python

1311번: 할 일 정하기 1 www.acmicpc.net 이 문제는 N명의 사람에게 N개의 일을 하나씩 담당하게 할 때 모든 일을 하는데 필요한 비용의 최솟값을 구하는 문제이다. 만약 단순히 모든 경우의 수를 고려해 일을 배..

wanna-be-developer-yjh.tistory.com

다만 이 문제는 사이클을 완성해야 하기 때문에 어떤 정점에서 시작하면 중간 경로에 해당 정점을 포함시키면 안 된다. 그러므로 이를 보완하기 위해 여러 조건들을 추가해 사이클의 비용만 계산하도록 함수를 수정한다.

이를 코드로 구현하면 다음과 같다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)
N = int(input())
D = []
for _ in range(N):
    D.append(list(map(int, input().split())))
dp = [[-1] * (1 << N) for _ in range(N)]
# u는 현재 방문한 정점, start는 사이클이 시작한 정점, vertices는 지금까지 방문한 정점의 개수이다.
def dfs(u, visited, start, vertices):
    global N
    if visited == (1 << N) - 1:
        return 0
    if dp[u][visited] != -1:
        return dp[u][visited]
    dp[u][visited] = sys.maxsize
    for v in range(N):
      	# 지금까지 방문한 정점의 개수가 N-1이면 시작 정점으로 되돌아가야 한다.
        # 단, 현재 정점에서 시작 정점까지의 간선이 존재해야 한다. 
        if vertices == N-1 and D[u][start] != 0:
            dp[u][visited] = D[u][start]
            break
        # 중간 경로에서 시작 정점을 지나면 안 된다.
        elif v != start and D[u][v] != 0 and (1 << v) & visited == 0:
            dp[u][visited] = min(dp[u][visited], dfs(v, visited | (1 << v), start, vertices + 1) + D[u][v])
    return dp[u][visited]
res = dfs(0, 0, 0, 0)
# 경로가 없는 경우 0을 출력한다.
if res == sys.maxsize:
    print(0)
else: print(res)