[코드트리][Python] 외판원 순회

https://www.codetree.ai/trails/complete/curated-cards/challenge-traveling-salesman-problem/description

Code Tree | Learning to Code with Confidence

 

코드

import sys

def find_route(cur_node, cur_num):
    global ans

    if cur_num == n and A[cur_node][0] != 0:
        ans = min(ans, sum(answer) + A[cur_node][0])
        return
    
    for next_node in range(n):
        if visited[next_node] or A[cur_node][next_node] == 0:
            continue

        answer.append(A[cur_node][next_node])
        visited[next_node] = True

        find_route(next_node, cur_num + 1)

        visited[next_node] = False
        answer.pop()

n = int(input())
A = [list(map(int, input().split())) for _ in range(n)]
ans = sys.maxsize
answer = []
visited = [False for i in range(n)]

visited[0] = True
find_route(0, 1)

print(ans)

 

풀이

처음 인상은 MST 문제인줄 알았습니다.

 

'근데 사이클을 만드는 것이기 때문에 MST는 아니다. 혹시 내가 모르는 응용 문제가  있나?' 라는 생각이 들었습니다.

MST는 사이클이 없는 경로에서 최소한의 비용으로 방문할 때 쓰는 것이기 때문에 다른 방법을 사용해야겠다는 생각이 들었습니다.

 

사실 더 생각해보니 아래와 같은 결론에 다다렀습니다.

MST는 사이클이 아니기 때문에 마지막 노드에서 첫 노드로 다시 돌아와야하는 추가 계산이 들어갑니다.

하지만 이것은 최소 경로를 반영하지 않는 추가 계산이 들어가는 것이기 때문에 부적절하다고 생각했습니다.

 

문제의 요구사항은 경로를 모두 백트래킹으로 구하고, 마지막 노드에서 첫 노드(1번 노드 고정)로 이동하는 경로를 더하여 최소한의 비용을 사용한 사이클을 답으로 제출하면 되겠다는 생각이 들었습니다.

 

따라서 완전 탐색 하는 김에 백트래킹을 통해서 모든 경로를 파악하기로 해결하였습니다.

 

문제의 요구사항은 항상 1번 노드에서 출발해서 만드는 사이클의 최소 비용을 찾는 것입니다.

 

고려해야하는 예외 사항은 아래와 같습니다.

- 가지 못하는 간선도 존재한다. -> 모든 간선이 이동할 수 있다는 전제는 없습니다.

- 순회를 할 수 있는가? -> 다시 1번으로 돌아올 수 있어야 사이클이 완성됩니다.