백준 10971 외판원 순회 2

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

10971번: 외판원 순회 2

 

몇문제안풀어봐서그런가 dfs개념이 너무 어려웠다.

 

먼져, 입력을 받는다.

 

dfs함수를 정의하는데, 이때 {

아직 방문x & 현재까지의 값이 answer보다 작음& arr[가장최근도시][갈도시]가 0이 아닌 경우에만

dfs를 수행하고, 아니면 무시한다.}

 

dfstmp=[]
def dfs(start,next,v=0): #시작도시, 최근방문도시, 지금까지의 value
    global answer #계속 업데이트할 정답값

    if len (dfstmp)==n:
        if arr[next][start]!=0: #마지막도시에서 첫도시로 못가는경우
            answer=min(answer,v+arr[next][start])

    for i in range(n):
        if i not in dfstmp and arr[next][i]!=0 and v<answer: # 방문x & 갈수있는길 & 정답보다 현재까지의v가 작을때만 수행
            dfstmp.append(i)
            dfs(start,i,v+arr[next][i])
            dfstmp.pop()
    return

    
n=int(input())
arr=[[*map(int,input().split())]for _ in range(n)]
answer=1e+10 #초깃값 큰 수
for i in range(n):
    dfstmp.append(i) #각각의 도시를 시작으로 dfs수행
    dfs(i,i)
    dfstmp.pop()

print(answer)