최적 경로

from itertools import permutations as pm

answer = -1


def simulate():
    result = 987654321
    perm = pm(clients)

    for item in perm:
        curX, curY = workplace[0], workplace[1]
        tempResult = 0
        for it in item:
            destX, destY = it[0], it[1]
            tempResult += abs(curX-destX) + abs(curY-destY)
            curX, curY = destX, destY
        tempResult += abs(curX-home[0]) + abs(curY-home[1])
        result = min(result, tempResult)

    return result


T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
    N = int(input())
    temp = list(map(int, input().split()))
    workplace, home, clients = [], [], [[] for _ in range(N)]
    cnt = 0

    for idx in range(0, len(temp), 2):
        x, y = temp[idx], temp[idx+1]
        if idx == 0:
            workplace.extend((x, y))
        elif idx == 2:
            home.extend((x, y))
        else:
            clients[cnt].extend((x, y))
            cnt += 1

    # 완전 탐색 (10! ~ 360만)
    answer = simulate()

    print("#" + str(test_case) + " " + str(answer))

D5

문제에서 대놓고 완전탐색을 하라고 가이드를 주었기 때문에,

여러분의 프로그램은 가장 짧은 경로의 이동거리만 밝히면 된다.

이 문제는 가장 짧은 경로를 ‘효율적으로’ 찾는 것이 목적이 아니다.

여러분은 모든 가능한 경로를 살펴서 해를 찾아도 좋다.

모든 경우를 체계적으로 따질 수 있으면 정답을 맞출 수 있다.

n=10, 순열(permuation) 사용 가능.

따라서 가능한 순열쌍을 전부 만들고 완전탐색을 돌리면서 답을 갱신하면 풀리는 간단한 문제였다.

만약, 효율성을 요하는 문제였다면 더 어려운 문제가 되었을 것이다.

출처: https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AYj2mga6ZewDFASl&contestProbId=AV15OZ4qAPICFAYD&probBoxId=AYj2mga6Ze0DFASl&type=PROBLEM&problemBoxTitle=%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98+Track+%28%EB%82%9C%EC%9D%B4%EB%8F%84+%EC%83%81%29&problemBoxCnt=6