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

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

10971번: 외판원 순회 2

 

🔥 작성 코드

def sol(tot, flag, s):
    global result
    # 여행비가 결과값보다 커지면 더 볼 필요가 없다.
    if tot >= result:
        return

    elif sum(v) == (N-1):
        # 마지막에 첫 출발지로 돌아가지 못하면 없는 경로, so 고려x
        if arr[flag][s] != 0:
            tot += arr[flag][s]
            if result > tot:
                result = tot
        return

    else:
        # 첫 출발지 s로 설정
        # s가 정해지면 flag(출발지)를 바꿔가며 여행 할 수 있는 도시(도착지, i)로 이동
        for i in range(N):
            if flag == -1:
                s = i
                sol(tot, i, s)
            elif v[i] == 0 and arr[flag][i] != 0 and i != s:
                v[i] = 1
                sol(tot+arr[flag][i], i, s)
                v[i] = 0
        return

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
v = [0 for _ in range(N)]

result = 10000000
flag = -1
tot = 0
s = -1
sol(tot, flag, s)
print(result)

 

⭕ 해설

1.  모든 도시를 첫 출발지로 여행했습니다.
2.  여행 비용을 지불한 목적지는 방문 배열v에 1로 바꾸어 저장했습니다.
3.  첫 출발지는 마지막 목적지가 되어야 하므로 함수 인자에 s로 추가하였습니다.
   • 여행 도중 s로 가지 못하게 설정
4.  마지막 목적지(== 첫 출발지)만 남았을 경우(v에 저장된 1의 개수가 N-1)에 함수를 종료하였습니다.
   • s로 갈 수 있다면 현 출발지에서 s로 가는 비용을 tot에 더해주고 result와 비교
   • 갈 수 없다면 그대로 종료
5.  여행 중간에 여행 비용이 결과값보다 커지면 여행을 그만두었습니다.