• 문제: https://www.acmicpc.net/problem/10971

설명

시작점을 정하고, 그 점에서 갈 수 있는 곳을 방문하여 들어간다.

이때 각 도시를 노드라고 설정하고 노드들의 관계를 보면 다시 원점으로 돌아가기 때문에 순환한다는 사실을 파악할 수 있다.
즉 순환하기 때문에 시작점이 어디가 되어도 상관없다.
0 -> 1 -> 2 -> 3 -> 1 은 10 + 9 + 12 + 8 이므로 39이고,
1 -> 2 -> 3 -> 0 -> 1도 9 + 12 + 8 + 10 이므로 39이기 때문이다.

코드

import sys
from sys import stdin as s

N = int(s.readline())
l = [list(map(int, s.readline().split())) for _ in range(N)]

visit = [False]*N
m = sys.maxsize

def dfs(depth, start, cost):
	global m
    
    # depth를 모두 거쳤고, 다시 원점으로 되돌아갈 수 있다면
    if depth == N-1 and l[start][0] != 0:
    	m = min(m, cost+l[start][0])
        return
        
	for i in range(N):        
    	# 아직 방문하지 않았고, 갈 수 있는 길이라면
    	if not visit[i] and l[start][i] != 0:
    		visit[i] = True
            dfs(depth + 1, i, cost+l[start][i])
            visit[i] = False

visit[0] = True 	# 방문표시
dfs(0,0,0)
print(m)