[백준] 외판원 순회 2

출처:: www.acmicpc.net/problem/10971

분류:: 브루트포스, DFS

 

1. 문제 이해 및 해결과정

- DFS로

 

2. 풀이방법

 1. [python] dfs

#외판원 순회 2
#https://www.acmicpc.net/problem/10971
import sys
sys.stdin = open("input.txt","r")
input=sys.stdin.readline
n=int(input())
arr=[list(map(int,input().split())) for _ in range(n)]
visited=[False]*n
res=1e9
def dfs(start,cur,cost): #시작점, 노드, 비용
    global arr,visited,res
    if visited.count(True)==n: #방문한 것이 노드의 개수와 같으면
        if arr[cur][start]!=0: #길이 있으면 
            res=min(cost+arr[cur][start],res)
    else:
        for next in range(n):
            if arr[cur][next] != 0 and visited[next]==False: #길이 있고, 방문안했으면
                visited[next]=True
                dfs(start,next,cost+arr[cur][next])
                visited[next]=False

for i in range(n):
    visited[i]=True
    dfs(i,i,0)
    visited[i]=False
print(res)

 

 

3. 오답원인

 

4. 알게된 점