백준 10971번 외판원 순환2

문제

접근

처음에는 단순하게 DFS 문제로 생각하고 풀었는데,
그러면 각 도시에서 시작하는 경우 한가지씩 밖에 고려를 못하기 때문에 모든 경우의 수를 다 확인할 수 있는 방법이 필요했다.

그래서 한 도시에서 시작해서 다시 시작한 도시로 돌아오면 재귀를 끝내는 것이 아니라 모든 경우의 수를 다 확인할 수 있게, 방문 여부를 체크하기 위한 리스트를 만들어서 처리했다.

코드

import sys

n = int(input())

costs = [[0] * n for _ in range(n)]
for i in range(n):
    costs[i] = list(map(int, input().split()))

def dfs(start, v, visited, value):
    global min_value

    if len(visited) == n:
        if costs[v][start] != 0:
            min_value = min(min_value, value + costs[v][start])
        return
    
    for i in range(n):
        if i != start and costs[v][i] != 0 and i not in visited:
            visited.append(i)             # 방문 처리를 하고,
            value += costs[v][i]
            dfs(start, i, visited, value) # 다음 도시로 이동,
            value -= costs[v][i]
            visited.pop()                 # 그 도시의 모든 경우를 확인 하고, pop -> 다음 도시로

min_value = sys.maxsize
for i in range(n):
    visited = [False for _ in range(n)]
    dfs(i, i, [i], 0)
    
print(min_value)