외판원 순회 2 풀이

문제 링크: https://www.acmicpc.net/problem/10971

백준 알고리즘 기초 2/2 520에서 5번째 - 10971번 외판원 순회 2를 풀어보았다.

 

풀이: dfs를 쓰는 전형적인 문제이다.

 

C++

 

Python

def dfs(st,cur,weight,cnt):
	global res
	if cnt==n:
		if inp[cur][st]:
			weight+=inp[cur][st]
			if res>weight: res=weight
			return
	if weight>res:
		return
	for i in range(n):
		if not visit[i] and inp[cur][i]:
			visit[i]=1
			dfs(st,i,weight+inp[cur][i],cnt+1)
			visit[i]=0
	

n=int(input())
inp=[list(map(int,input().split())) for i in range(n)]
res=100000000
visit=[0]*n
for i in range(n):
	visit[i]=1
	dfs(i,i,0,1)
	visit[i]=0
print(res)

Java