[백준] 10971 외판원 순회 2

정답코드

# 외판원 순회 2
# 복습 횟수:0, 00:45:00, 복습필요O
import sys
si = sys.stdin.readline
N = int(si())
graph = [list(map(int, si().split())) for i in range(N)]
visited = [0 for i in range(N)]
answer = sys.maxsize
def dfs(first, start, count, sumi):
    global answer
    if count == N-1: 
        if graph[start][first] == 0: return

        answer = min(answer, sumi + graph[start][first])
        
        return
    
    for i in range(N):
        if visited[i]: continue
        if graph[start][i] == 0: continue

        visited[i] = 1
        tmp = graph[start][i]
        dfs(first, i, count + 1, sumi + tmp)
        visited[i] = 0
    return

for i in range(N):
    visited[i] = 1
    dfs(i, i, 0, 0)
    visited[i] = 0

print(answer)

 

풀이

1. 마지막엔 맨 처음으로 돌아와야 하므로 first에 인자로 두었습니다. 이후 count == N-1을 통해 모든 도시를 돈 경우 처음으로 돌아갈 수 있게 하였습니다.

 

2. 백트래킹을 사용하였습니다.

 

3. visited로 탐색한 도시를 체크하였습니다.