백준 10971번 - 외판원 순회2

출처 : 10971번: 외판원 순회 2 (acmicpc.net)

10971번: 외판원 순회 2

외판원 순회 2 성공분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초

256 MB

25806

9316

5530

34.588%

문제

외판원 순회 문제는 영어로 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 ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

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

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

 

---

[ 문제 설명 ]

 

n개의 도시를 순회하고 다시 돌아올 때의 최소 비용을 묻는 문제입니다.

 

간단하게 재귀를 통한 순회 롬 문제를 구현할 수 있습니다.

 

코드를 보시면 아! 하실 겁니다.

 

혹시 모르니 코드에 주석으로 설명하겠습니다.

 

---

[ 코드 ]

 

import sys

input = lambda: sys.stdin.readline().strip()

n = int(input())
w = [list(map(int, input().split())) for i in range(n)]
visit = [0] * n
m = 1e10


def goSalesman(N, C):
    # print(N, C)
    global n, w, visit, m
    if C < m:  # else 의 경우는 이제 까지의 비용의 합인 m 값보다  C가 더 크다면 볼필요도 없는 경우!
        # 파이썬 all 함수는 iterable한 객체의 모든 값이 참일 때 참을 반환 하는 함수 입니다.
        # 즉, 모드 순회하고, n == 0 으로 다시 돌아온 경우에 그 값을 반환 하는 것 입니다.
        if all(visit) and N == 0:  
            m = min(m, C)
            print(visit)
            # print(m)
        # 재귀를 통한 가중치 계산
        for i in range(n):
            if w[N][i] > 0 and not visit[i]:
                visit[i] += 1
                goSalesman(i, C + w[N][i])
                # else 로 빠져 나온 경우.
                visit[i] -= 1


goSalesman(0, 0)
print(m)

---

후기

 

알면 쉬운데

알지 못했을 때는 무언가 막막한 문제