https://www.acmicpc.net/problem/10971
10971번: 외판원 순회 2첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 jwww.acmicpc.net
몇문제안풀어봐서그런가 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)