SWEA-1247-최적 경로

회사 좌표, 자택 좌표, 방문해야 할 고객 집들의 좌표 가 주어진다
순서는 회사, 방문해야 할 고객 집들, 자택 순으로 방문해야한다
이 방문 순서 중 최단 경로를 찾아야 함

• 완전탐색을 하기 위해 DFS를 사용함
• 처음은 반드시 회사에서 출발해야하기 때문에 회사 좌표를 준다
• 마지막은 반드시 집으로 도착해야하기 때문에 DFS에서 마지막 처리는 마지막 방문 고객의 집에서 자택 까지의 거리를 더해준다.

test_case = int(input())


def reculsion(n, d, depth):
    global MIN

    if MIN <= d: return # 여태까지 계산한 거리가 현재 까지 탐색한 최솟값보다 크다면 더 이상 계산할 필요가 없음

    if depth == N-2:
        if MIN > d+abs(A[2*n] - A[2]) + abs(A[2*n+1] - A[3]): # 마지막 고객 집에서 본인 집까지의 거리를 더해 최소값이 맞는지 확인
            MIN = d+abs(A[2*n] - A[2]) + abs(A[2*n+1] - A[3])
        return

    for i in range(2, N):
        if V[i] == False:
            V[i] = True
            reculsion(i, d+abs(A[2*n] - A[2*i]) + abs(A[2*n+1] - A[2*i+1]), depth+1)
            V[i] = False


for T in range(1, test_case+1):
    N = int(input())+2
    A = list(map(int, input().split()))
    V = [False for _ in range(N)]
    MIN = 2000
    reculsion(0, 0, 0)
    print('#{} {}'.format(T, MIN))