백트래킹 - 10971번

외판원 순회 2 (10971번)

💡 문제 아이디어

• 시작하는 도시 와 방문하려는 도시 , 비용, 방문했던 도시들의 리스트 를 받아서 재귀함수 만들기

👀 풀이

import sys

N = int(sys.stdin.readline()) 
graph = [0]*N

for i in range(N) :
  graph[i] = list(map(int, sys.stdin.readline().split()))

ans = 1e9

def f(start , next , cost, visited) : 
# start : 맨 처음 도시
# next : 방문하려는 도시
  global ans
  if len(visited) == N :
    if graph[next][start] != 0 :
      ans = min(ans , cost + graph[next][start])
    return
  for i in range(N) : # 그 다음에 갈 도시 
    if graph[next][i] != 0 and i not in visited and cost<ans :
      visited.append(i)
      f(start, i , cost + graph[next][i] , visited)
      visited.pop()

for i in range(N) :
  f(i , i , 0, [i]) # 일단 시작한 곳은 이미 방문한 것이므로 [i] 

print(ans)

• 젤 처음으로 시작하는 도시는 N 개임
• 이때, 도시로 이동하는 비용(cost)이 최저비용(ans) 보다 클 경우 굳이 방문할 필요 없이 끝낼 수 있다. --> 이 부분이 시간초과 에 영향을 줌 !!