백준 10971번 : 외판원 순회 2 (Python)

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

n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]

min_cost = int(1e9)
visited = [False] * n

# now : 현재 방문 중인 도시
# now_cost : 지금 도시까지 비용
# visits_cnt : 지금까지 방문한 도시 수
def back_track(now, now_cost, visits_cnt) :
    global min_cost
    # 지금까지 비용이 최소 비용보다 크면 더 이상 탐색 X
    if now_cost >= min_cost :
        return
    # 모든 도시 다 방문하면 처음 시작한 도시로 돌아가야 함
    if visits_cnt == n :
        # 시작 도시까지 길이 있으면 현 비용과 최소 비용 비교해 최소 비용 갱신
        if graph[now][start] != 0 :
            min_cost = min(min_cost, now_cost + graph[now][start])
        return
    
    for i in range(n) :
        # 방문하지 않은 도시 i에 대해 현재 도시로부터 길이 있으면 방문
        if visited[i] == False and graph[now][i] != 0 :
            visited[i] = True
            back_track(i, now_cost + graph[now][i], visits_cnt + 1)
            visited[i] = False
            
# 시작 도시는 고정            
visited[0] = True
start = 0
back_track(0, 0, 1)

print(min_cost)

가능한 모든 루트를 탐색한다.

탐색 종료 조건은 3가지

- 현재 탐색 중인 도시까지의 비용이, 기존에 저장된 최소 비용보다 크다면 탐색 종료

- 모든 도시 탐색 , 마지막 도시에서 처음 도시로 돌아갈 수 없으면 탐색 종료

- 모든 도시 탐색 후, 처음 도시로 돌아갈 수 있으면 현재의 비용과 저장된 최소 비용 비교해 최소 비용 갱신

탐색 종료 조건에 해당하지 않으면, 방문하지 않았고 현재 방문 중인 도시에서 길이 있는 도시를 순차적으로 방문한다.

 

탐색 시작 도시는 어떤 도시로 지정하든 상관이 없다.

모든 도시를 '순회'하기에 시작 도시가 무엇이든 하나의 순회 루트에서의 비용은 동일하기 때문이다.

따라서 시작 도시를 고정하면 탐색에 들어가는 시간이 크게 절약된다.

 

물론 itertools의 permutations를 쓰면 코드는 짧아지지만 시간은 훨씬 더 필요하다.