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

입력

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

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

출력

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

---

풀이

문제를 보고 어떤 방법으로 접근할지 생각한 결과 입력되는 N의 범위가 2 <= N <= 10, 시간 제한이 2초인 것을 보고 모든 경우의 수를 체크해봐도 되겠다고 판단하였다

 

시작한 도시로 돌아와야한다는 조건이 있었기에 길이가 N인 인덱스 수열을 생성하고 생성된 수열을 반복문을 통해

W[i-1인덱스 값][i인덱스 값] 으로 접근하여 순회에 필요한 비용을 계산하려한다

 

# 인덱스를 순열화하여 모든 경우 계산
def recursion(idx,N):
    if idx==N:
        check[N] = check[0]
        cost(check)
        return
    for i in range(N):
        if used[i]:
            continue
        used[i]=True
        check[idx] = i
        recursion(idx+1,N)
        used[i]=False

입력받은 N값의 범위에 해당하는 모든 순열을 생성한다

check[N] = check[0]을 대입하여 출발한 도시로 돌아오도록 순열을 설정한다

시간복잡도는 N!*N으로 N의 값이 최대 10이기에 10!*10으로 약 3천만

 

# 순회 비용 계산
def cost(check_in):
    sum = 0
    global res
    for i in range(1,N+1):
        tmp = W[check_in[i-1]][check_in[i]]
        if tmp==0: # 길이 없는 경우
            return
        else:
            sum += tmp
    if res<0: # 초기값 설정
        res = sum
    elif res > sum:
        res = sum

넘겨받은 순열리스트를 통해 순회값을 계산한다

도시간 이동 비용이 0인지 확인하여 길이 존재하는지 검토한다

전역변수 res의 초깃값을 -1로 설정하여 첫 순열의 값을 대입한다

 

순회값을 계산하는 부분의 시간복잡도가 O(N)이기에 앞서 순열을 생성한 O(N!*N)에 N이 곱해져 최대 3억회에 가깝게 계산되기에 시간 초과가 날 것이라고 예상했다

실제로 W[check_in[i-1]][check_in[i]] 를 tmp에 대입하여 사용하지 않고 2회 접근하는 코드에서는 시간초과가 났고 변수를 통해 메모리 접근횟수를 줄이는 것도 시간을 줄이는 중요한 역할이라는 것을 다시금 깨닫는 기회였다