[알고리즘] 백준10971 외판원 순회2 - 파이썬

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

10971번: 외판원 순회 2

 

 

 

[풀이 코드]

from sys import stdin
input = stdin.readline

N = int(input())

graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))


def dfs(i):
    if False not in visited:
        result.append([sum(s), i])

    for x in range(len(graph[i])):
        if not visited[x] and graph[i][x] > 0: #방문한적없고 0이 아닌 경우
            visited[x] = True
            s.append(graph[i][x])
            dfs(x)
            s.pop()
            visited[x] = False

sum_result = []
for start in range(N):
    result = []
    s = []
    visited = [False] * N
    visited[start] = True
    dfs(start)
    visited[start] = False

    for total, end in result: # 마지막 방문 end -> start의 값도 더해준다.
        if graph[end][start] != 0:
            total += graph[end][start]
            sum_result.append(total)

print(min(sum_result))

• 이동하는데 드는 비용이 2차원 행렬로 입력이 주어진다. dfs내에서 graph [x]!= 0 부분을 graph[i][x] > 0 로 고쳐주니 잘 작동했다.. 2차원 배열을 할 때마다 실수하는 것 같은데 주의해야겠다.
  
  
•  먼저, 맨 마지막 도시에서 처음 출발했던 도시로 돌아오는 부분을 마지막 for문에서 처리를 해주는데 이를 위해서 dfs함수 내에서 result함수에 마지막 방문 도시를 같이 append 해준다. 그리고 dfs탐색이 끝나면 마지막 도시에서 처음 도시로 이동하는 비용을 더해 총 구해진 비용 중 최솟값을 구한다.