[Python] SW Expert Academy #1247 최적 경로

📚문제: #1247 최적 경로(D5)

전체 코드

# 1247. 최적 경로
 
# 전역변수
global min_dist
 
# 가장 짧은 경로, 백트래킹 함수
def backtracking(v, b, cnt, dist):
 
    global min_dist
         
    for i in range(N):
             
        # 아직 방문하지 않은 고객
        if not v[i]:
 
            # 회사에서 출발할 때
            if cnt == 0:
                 
                cp_r, cp_c = company
                c_r, c_c = cl[i]
                 
                dt = abs(cp_r-c_r) + abs(cp_c-c_c)
 
                # 방문처리
                v[i] = True
                 
                # 백트래킹 함수 재귀호출
                backtracking(v, i, cnt + 1, dist + dt)
                 
                # 백트래킹 함수 종료 후 원복
                v[i] = False
             
            else:
                 
                # 방문처리
                v[i] = True
                 
                # 이전 고객 좌표
                b_r, b_c = cl[b]
                 
                # 현재 고객 좌표
                cur_r, cur_c = cl[i]
                 
                dt = abs(b_r-cur_r) + abs(b_c-cur_c)
                 
                # 백트래킹 함수 재귀호출
                backtracking(v, i, cnt + 1, dist + dt)
                 
                # 백트래킹 함수 종료 후 원복
                v[i] = False
                  
        # 마지막 고객을 방문하고 집으로 갈 때  
        if cnt == N:
             
            h_r, h_c = home
            c_r, c_c = cl[b]
             
            dt = abs(h_r-c_r) + abs(h_c-c_c)
             
            min_dist = min(min_dist, dist + dt)
            return
     
# 테스트케이스의 개수
T = int(input())
 
# 각 테스트 케이스 실행
for t in range(1, 10+1):
 
    # 테스트 케이스마다 초기화
    min_dist = int(1e10)
     
    # 고객의 수
    N = int(input())
     
    # 방문 여부 리스트
    visited = [False] * N
     
    # 회사 좌표, 집 좌표, N명의 고객 좌표
    coords = list(map(int, input().split()))
 
    # 회사
    company = [coords[0], coords[1]]
      
    # 집
    home = [coords[2], coords[3]]
     
    # N명
    clients = coords[4:]
     
    cl = []
     
    for i in range(0, 2*N, 2):
         
        cl.append([clients[i], clients[i+1]])
     
    # 함수 실행
    backtracking(visited, -1, 0, 0)
     
    # 답안 출력
    print("#{} {}".format(t, min_dist))