アルゴリズム(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.210082055413818秒…^^今...?
私はもっと無知ではない解決策を考えるべきだ.
sol 2)DFSによる完全ナビゲーション
DFSFによる完全ナビゲーション
コメントコード