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

티스토리 메뉴 펼치기 댓글수0

프로그래밍/삼성 SWEA

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

snoopybox
댓글수0

나의 풀이 :

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++이 최적의 언어인 듯.

맨위로

https://www.snoopybox.co.kr/2011

신고하기