[백준`S2] 10971 - 외판원 순회 2 (Python)

문제 설명

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

10971번: 외판원 순회 2

 

---

문제 풀이

시간초과 때문에 힘들었던 문제.. 이게 파이썬의 한계인가

처음에는 count가 n일 때 route 배열에 있는 순서대로 cost를 더해주면서 값을 구하고,

총 비용과 minCost를 비교하는 방법으로 코드를 짰었는데 시간초과가 걸렸다

 

파라미터로 cost를 더하면서 넘겨주고 minCost와 파라미터로 넘어온 cost를 비교해서

더 낮은 값을 minCost 처리 해주었다

 

count가 0일 때는 route 배열이 비어있기 때문에 route[count-1]를 처리해줄 수 없어

count가 0이거나, 방문하지 않았으면서 count-1에서 i로 가는 비용이 0이 아닐 때 재귀해주었음

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [False] * n
route = []
minCost = 1e10


def dfs(count, cost):
    global minCost
    if count == n:
        if graph[route[-1]][route[0]] != 0:
            minCost = min(cost + graph[route[-1]][route[0]], minCost)
        return

    for i in range(n):
        if count == 0 or (not visited[i] and graph[route[count - 1]][i] != 0):
            route.append(i)
            visited[i] = True
            dfs(count + 1, cost + graph[route[count - 1]][i])
            route.pop()
            visited[i] = False


dfs(0, 0)
print(minCost)