1. 문제 설명

외판원 순회 2

2. 문제 분석

DFS 및 백트래킹을 통해 출발 노드에서 출발, 도착 노드가 같다면 그때까지 방문한 도시 개수를 카운트해 최솟값을 갱신한다.

• 이때 로컬 최솟값과 다음에 방문한 노드 비용을 비교해야 시간 초과를 피할 수 있다. 파이썬으로 풀 때에는 이 부분으로 인해 계속 시간 초과가 났고, 검색 이후에야 찾을 수 있었다. 백트래킹과 같이 재귀를 사용한 부분에서는 조건문 하나로도 시간 초과 여부가 결정된다는 데 주의하자.

3. 나의 풀이

import sys

n = int(sys.stdin.readline().rstrip())
nodes = []
for _ in range(n):
    nodes.append(list(map(int, sys.stdin.readline().rstrip().split())))

def DFS(cur_node, start_node, cost, visited_cnt):
    global ans
    if cur_node == start_node and visited_cnt == n:
        ans = min(ans, cost)

    for i in range(n):
        if not visited[i] and nodes[cur_node][i] != 0 and cost < ans:
                visited[i] = True
                visited_cnt += 1
                DFS(i, start_node, cost+nodes[cur_node][i], visited_cnt)
                visited[i] = False
                visited_cnt -= 1


ans = sys.maxsize
visited = [False for _ in range(n)]

for i in range(n):
    DFS(i, i, 0, 0)
print(ans)