[백준/Python]10971_외판원 순회 2

문제

https://www.acmicpc.net/problem/10971

10971번: 외판원 순회 2

풀이

각 도시에서 시작하여 모든 도시를 방문하고 다시 처음 도시로 돌아오는 한붓그리기 문제다.

간선의 비용이 다르고 경로의 정보를 저장해야하기 때문에 DFS를 사용한다.

외판원 최소 순회 비용인 min_value는 10억으로 초기화 한다.

start: 시작 노드, current: 현재 노드, value: 현재 노드까지 쓴 비용, visited: 경로

DFS 종료 조건

: matrix의 0은 연결이 안됨을 의미하기 대문에 len(visited) == n일 때, current에서 start로 가는 길인 matrix[current][start]가 0이 아니여야 한다.

코드

import sys


def dfs(start, current, value, visited):
    global min_value
    if len(visited) == n:
        if matrix[current][start] != 0:
            min_value = min(min_value, value + matrix[current][start])
        return
    for i in range(n):
        if matrix[current][i] != 0 and i not in visited:
            visited.append(i)
            dfs(start, i, value + matrix[current][i], visited)
            visited.pop()


n = int(sys.stdin.readline().rstrip())
matrix = []
min_value = int(1e9)
for _ in range(n):
    matrix.append(list(map(int, sys.stdin.readline().rstrip().split())))
for i in range(n):
    dfs(i, i, 0, [i])
print(min_value)