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

나의 풀이 :

def get_distance(P, Q):

return abs(P[0]-Q[0]) + abs(P[1]-Q[1])

def travel(total, idx):

global ans

if total >= ans:

return

last_visit = customers[idx]

if len(visited) == len(customers):

ans = min(ans, total + get_distance(last_visit, home))

return

for i in range(len(customers)):

if i in visited:

continue

visited.add(i)

this_visit = customers[i]

travel(total + get_distance(last_visit, this_visit), i)

visited.remove(i)

T = int(input())

for tc in range(1, T + 1):

N = int(input())

points = list(map(int, input().split()))

office = (points[0], points[1])

home = (points[2], points[3])

customers = [office]

for x in range(4, 2*N+4, 2):

customers.append(tuple(points[x:x+2]))

ans = float('INF')

visited = set((0,))

travel(0, 0)

print('#{} {}'.format(tc, ans))

한마디 :

이 문제는 풀었지만, SWEA의 많은 문제들이 Python으로 풀리지 않는다. 입출력 속도가 너무 느려서 그런데 sys.stdin을 사용할 수 없게 막아놨다. 알고리즘 풀이용으로는 C++이 최적의 언어인 듯.