[백준] 외판원 문제2 (TSP)

[백준] https://www.acmicpc.net/problem/10971
[참고] https://shoark7.github.io/programming/algorithm/introduction-to-tsp-and-solve-with-exhasutive-search

[완전탐색]

[문제 정의]

출력

start에서 출발해 next를 거쳐 N개의 도시를 방문한 후 start 도시로 되돌아오기까지 걸리는 거리의 패턴 중 최솟값을 구해라

문제에서 주어지는 값

도시 개수 N, 한 도시에서 다른 도시까지의 거리 dist

재귀함수 한 턴이 하는 일

현재 도시(next)에서 다음으로 갈 도시(for문 중 i)를 정하고 거리를 더하는 것.

재귀함수에 필요한 인자

(도시 개수: N)
start 도시의 idx : start
next 도시의 idx : next
visited 도시 list : visited =[]
현재까지 온 거리 cost: cost

재귀 리턴 조건

모든 도시 방문

재귀 반복 코드

for 0부터 n-1까지 n개의 도시로 가는 경로를 탐색

도시 방문 가능 조건

• 이전에 방문한 적 없음 => (visited list 확인)
• 그 도시로 가는 길이 있어야 함 => (dist[next][i] 확인)

# ----[input]-------------------------------------------------
import sys
sys.stdin = open('text/TSP.txt', 'r')
n = int(input())
dist =[]
for i in range(n):
	dist.append(list(int(i) for i in input().split()))
# -----------------------------------------------------------

min = 9999999

def dfs(start, next, visited, cost):
	global min

	if len(visited) == n:
		# 리턴 조건: 모든 도시 방문함?
		if dist[next][start] != 0:
			cand = cost + dist[next][start]	# 최소거리 후보
			min = min if cand > min else cand			# 둘 중 작은 값 택
		return

	else:
		# 아직 안함
		for i in range(n):
			if dist[next][i] != 0 and i not in visited:
				# and i != start 참고 코드에 이게 포함되어있는데 없어도 될 것 같음
				# 어차피 처음 함수 호출할 때 시작도시를 visited에 넣으니까
				visited.append(i)
				dfs(start, i, visited, cost + dist[next][i])
				visited.pop()

# 각 도시마다 시작
for i in range(n):
	# 시작도시를 저장하는 start변수와 별개로 next는 현재 위치한 도시를 의미하므로
	# 처음 함수를 호출할 때는 start와 next를 똑같이 할당해야 한다.
	dfs(i, i, [i], 0)

print(min)