[삼성 SW 역량테스트] 1247. 최적 경로 / D5

https://swexpertacademy.com/main/code/problem/problemDetail.do

SW Expert Academy

tc = int(input())

def dist(p1, p2):
    return abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])

def dfs(count, order, visited):
    global answer
    if count == n:
        total = dist(company, clients[order[0]])
        for i in range(len(order)-1):
            total += dist(clients[order[i]], clients[order[i+1]])

        total += dist(clients[order[-1]], house)
        if total < answer:
            answer = total
        return

    for i in range(n):
        if not visited[i]:
            visited[i] = True
            dfs(count + 1, order + [i], visited)
            visited[i] = False
for t in range(tc):
    n = int(input())
    points = list(map(int, input().split()))
    company = [points[0], points[1]]
    house = [points[2], points[3]]
    clients = []
    for i in range(4, len(points), 2):
        clients.append([points[i], points[i+1]])

    lst = [x for x in range(n)]

    answer = 10**8
    visited = [False for _ in range(n)]
    dfs(0, [], visited)
    print("#{0} {1}".format(t+1, answer))

외판원 순회(TSP: Traveling Salesperson Problem)로 잘 알려진 문제다. 하지만 풀어본 건 처음이었다.

일부러 itertools 라이브러리를 쓰지 않고 풀어보았다.