백준 10971 외판원 순회2 파이썬

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

 

예제 입력	예제 출력
4 0 10 15 20 5 0 9 10 6 13 0 12 8 8 9 0	35

 

문제 바로가기

---

DFS

깊이 우선 탐색으로, 너비 우선 탐색(BFS)와 대비된다. 루트 노드 혹은 임의의 노드에서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.

 

완전 탐색

하나의 도시로 시작해서 전체 탐색을 하는 완전 탐색(브루트 포스) 방법을 선택했다. 각 도시에서 출발하여 마지막 도시일 때 (종료 조건) 비용을 계산하고 리턴하도록 구현했다.

 

함수 분석

시작 도시(start)를 계속 가지고 가는 이유는 마지막 도시에서 시작 도시로 돌아올 수 있는지 확인하기 위함이다.

---

전체 코드

import sys
input = sys.stdin.readline

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

visited = [False] * n
minvalue = sys.maxsize

# 몇번째 방문인지, 시작 도시, 현재 도시, 비용
def travel(cnt, start, now, cost):
    global minvalue

    # 만약 마지막 도시이며 시작한 도시로 되돌아갈 수 있다면
    if cnt == n and city[now][start]:
        cost += city[now][start]

        if cost < minvalue:
            minvalue = cost
            return
        
    for i in range(n):
        # 만약 방문한 도시가 아니고 갈 수 있다면
        if not visited[i] and city[now][i]:
            visited[i] = True
            travel(cnt+1, start, i, cost+city[now][i])
            visited[i] = False

for i in range(n):
    visited[i] = True
    travel(1, i, i, 0)
    visited[i] = False

print(minvalue)