10971. 외판원 순회

백트래킹 문제이다.

문제의 핵심은 사이클이 만들어지기 때문에 어디서 시작해도 같은 사이클을 가지게 되니 시작 지점을 고정해놓아도 상관이 없다는 것이다. 따라서 무조건 0으로 시작하도록 고정하였다.

또 하나 내가 실수한 점이 있는데, 함수 안에서 cost 함수를 대입연산자를 사용하여 더해지는 경우, 그 함수 내에서 cost 값이 i가 변할 때마다 누적된다는 것을 간과하였다. 

이 문제를 해결하기 위해서는 cost값에 대입연산자를 사용하여 더하지 말고 함수 호출 시에만 더해주어야 한다.

 

import sys
input = sys.stdin.readline

def get_routine(start, cnt, cost) :
    global min_cost
    if cost > min_cost :
        return
    if cnt == n-1 :
        if w[start][0] != 0 :
            min_cost = min(min_cost, cost+w[start][0])
        return
    for i in range(1, n) :
        if check[i] == False and w[start][i] != 0 : 
            check[i] = True
            get_routine(i, cnt+1, cost+w[start][i])
            check[i] = False


n = int(input())

w = [list(map(int, input().split())) for _ in range(n)]
min_cost = 10**8
check = [False for _ in range(n)]
get_routine(0, 0, 0)
print(min_cost)