알고리즘(Python)

1247. [S/W 문제해결 응용] 3일차 - 최적 경로

문제링크

sol 1)
문제에도 그렇고 댓글에도 그렇고 완전탐색으로 풀어도 가능하다길래 함 해봤다. 아래 같이

import time
st = time.time()
import itertools
t = int(input())
for test in range(t):
    n = int(input())
    xy = list(map(int, input().split()))
    start = xy[:2]
    end = xy[2:4]
    x = [xy[i] for i in range(4, n*2+4) if i%2==0]
    y = [xy[i] for i in range(4, n*2+4) if i%2!=0]
    arr = [i for i in range(n)]
    per = list(itertools.permutations(arr, n))
    costlist = []
    # 각 순열조합마다 계산
    for case in per:
        before_x = start[0]
        before_y = start[1]
        cost = 0
        # 순열조합 안에서 고객-고객사이의 거리계산
        for i in case:
            cost += abs(x[i]-before_x) + abs(y[i]-before_y)
            before_x = x[i]
            before_y = y[i]
        # 마지막 고객 - 집 사이의 거리 비용 계산
        cost += abs(end[0]-before_x) + abs(end[1]-before_y)
        costlist.append(cost)
    print('#{} {}'.format(test+1, min(costlist)))
print(time.time() - st)

내가 봐도 복잡하긴 하다.

시간제한은 python은 30초였는데, 위의 코드론 134.21008205413818 초 걸렸다...^^ 시롸....?

좀 더 무식하지 않은 솔루션을 생각해봐야했다.

sol2) DFS를 이용한 완전 탐색

DFSF를 이용해서 완전탐색을 해보자
참고코드