[ 백준 10971 ] 외판원 순회 2 - Python

문제 보기

이 문제는 TSP(Traveling Salesman problem) 문제이다.

 

여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것이다.

 

한 붓 그리기로 유명한 해밀턴 경로와 유사하며, 다시 출발점으로 돌아오는 코드만 추가하면 된다.

 

풀이 과정은 아래 순서를 따르며 dfs를 통해서 구현하였다.

1. 각 번호에서 출발하여 제자리로 돌아오는 값을 구한다.

2. 1번 과정을 반복하면서 최솟값을 업데이트한다.

---

 

코드

import sys


def dfs(start, next, value, visited):
    global min_value

    if len(visited) == N:
        if travel[next][start] != 0:
            min_value = min(min_value, value + travel[next][start])
        return

    for i in range(N):
        if travel[next][i] != 0 and i != start and i not in visited:
            visited.append(i)
            dfs(start, i, value + travel[next][i], visited)
            visited.pop()


if __name__ == "__main__":

    N = int(input())
    travel = [list(map(int, input().split())) for _ in range(N)]

    min_value = sys.maxsize

    # 각 번호에서 시작
    for i in range(N):
        dfs(i, i, 0, [i])

    print(min_value)

 

※ dfs 함수에서 min_value보다 이미 값이 큰 경우는 무시하는 것이 더 빠르게 결과를 도출할 수 있습니다.