[Python] Baekjoon - 10971. 외판원 순회 2

외판원 순회 문제는 TSP(Traveling Salesman Problem)라고 불리며 CS 분야에서 중요하게 취급된다. 백준 10971번 외판원 순회 2 문제는 TSP의 가장 일반적인 형태이다. 백트래킹과 브루트 포스 알고리즘을 통해 해결할 수 있으며 난이도는 실버 2이다.

 

백준 10971번 외판원 순회 2 문제 정보

알고리즘 분류

- 백트래킹, 브루트포스

난이도

- 실버 2

 

외판원 순회 2 문제 요약

양방향 가중치 그래프에 대해, 시작점에서 다른 모든 노드를 거쳐 다시 시작점으로 돌아오는 최단거리를 구하는 문제다.

문제 풀이 과정

• DFS를 사용하여 모든 노드를 방문하고, 마지막에 다시 시작점으로 돌아오는 거리를 합하여 최단거리를 찾음
• 중간에 더 이상 갈 수 있는 곳이 없으면 (현재 노드에서 다른 방문할 수 있는 노드가 없으면) 되돌아가므로 백트래킹 알고리즘에 해당

 

코드

def dfs(node, dist, cnt):
    global N, weights, visited, shortest

    # N개 노드 모두 방문했으면 시작점으로 되돌아가기
    if cnt == N:
        if weights[node][0] > 0:
            shortest = min(shortest, dist + weights[node][0])
        return

    # 이웃한 노드 중 방문하지 않은 노드 방문
    for idx, w in enumerate(weights[node]):
        if w > 0 and not visited[idx]:
            visited[idx] = 1
            dfs(idx, dist+w, cnt+1)
            visited[idx] = 0


if __name__ == '__main__':
    N = int(input())
    weights = []
    visited = [0 for _ in range(N)]
    shortest = float('inf')
    for _ in range(N):
        weights.append(list(map(int, input().split())))

    visited[0] = 1
    dfs(0, 0, 1)
    print(shortest)