[백준] 10971번: 외판원 순회 2 (python)

https://www.acmicpc.net/problem/10971

---

처음에는 최소 비용이라는 단어만 보고 무작정 BFS로 풀었다가 시간 초과로 못푼 문제.

DFS로 순회를 하며 지금까지의 최소 비용보다 비용이 높다면 다시 그 전으로 돌아가 백트래킹을 하여 문제를 해결하였다.

순회가 종료되었음을 확인하는 조건을 생각해내지 못해서 검색을 통해 풀었다.

끝까지 순회를 한 뒤 마지막 지점에서 다시 출발 점으로 갈 수 있는지 확인하면 되는 간단한 방법이었다...

DFS에 좀 더 익숙해져야 할 필요가 있다.

---

from collections import deque

n = int(input())
costs = [list(map(int, input().split())) for _ in range(n)]
# 최소 비용
min_cost = 1e8

def dfs(start, next_, cost, visited):
    global min_cost
    
    # 모든 도시 순회를 하였는지 확인
    if False not in visited:
    	# 마지막 도시에서 다시 출발지로 올 수 있는지 확인
        if costs[next_][start] > 0:
        	# 마지막 도시에서 출발지로 오는 비용을 합쳐 최소 비용 갱신
            min_cost = min(min_cost, cost + costs[next_][start])
        return min_cost
    
    # 모든 도시를 순회
    for i in range(n):
    	# 도시끼리 연결되었는지, 이미 방문한 도시인지, 현재 비용이 최소 비용보다 큰지 확인
        if (costs[next_][i] > 0) and (not visited[i]) and (cost < min_cost):
            visited[i] = True
            dfs(start, i, cost + costs[next_][i], visited)
            # 만약 순회가 끝났다면 다시 방문 해제
            visited[i] = False

# 출발지가 정해져 있지 않아 모든 도시로 시작하는 방법을 모두 순회
for i in range(n):
    visited = [False] * n
    visited[i] = True
    dfs(i, i, 0, visited)

print(min_cost)