소스코드

import sys
input = sys.stdin.readline
N = int(input())
graph = [list(map(int, input().strip().split())) for _ in range(N)]

visited = [False] * N
min_cost = float('inf')
def solve(start, current, depth, cost):
	global visited
	global min_cost
	
	# 이미 비용이 더 비싸면 더이상 재귀 안 하기
	if cost >= min_cost:
		return
	
	if depth == N:
		# 다시 원점으로 복귀하는 시점
		if graph[current][start] != 0:
			min_cost = min(min_cost, cost + graph[current][start])
		return 
	
	for next_city in range(N):
		if not visited[next_city] and graph[current][next_city]:
			visited[next_city] = True
			solve(start, next_city, depth+1, cost + graph[current][next_city])
			visited[next_city] = False
			
for i in range(N):
	visited[i] = True
	solve(i,i,1,0)
	visited[i] = False
	
sys.stdout.write(str(min_cost) + '\\n')

풀이

• 시작 도시가 따로 있는 게 아니므로 모든 도시를 시작점으로 삼아야 합니다.
• 그래프(지도)를 만들어야 합니다.
• 매 경우의 수마다 방문한 적 있는 도시는 방문하면 안되므로 visited 같은 방문 여부를 체크하기 위한 자료구조가 필요합니다.
• 각 경우의 수가 방문한 적이 없는 도시로 순회를 해야하지만, 마지막에는 시작 노드로 돌아와야하므로 재귀함수가 시작노드에 대한 정보를 알아야 합니다. 이를 함수의 인자로 전달합니다. 마지막이 언제인지도 알아야하므로, 재귀함수의 깊이가 N에 도달한 경우에 처리할 수 있도록 depth라는 인자를 사용합니다.
• 다음 목적지로 이동하기 위해서는 현재 도시의 정보를 알아야합니다. 이를 함수의 인자로 전달합니다.
• visited는 한 번만 사용하는 것이 아닙니다. 여러 번 실행되는 동안 계속 사용되고 있습니다. 그러므로 재귀함수 실행 이전엔 방문처리를 하고, 실행 이후에는 방문 처리를 해제해야 합니다.