[SWEA][Python3] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로
2019. 5. 9. 00:15 |
프로그래밍/삼성 SWEA
나의 풀이 :
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++이 최적의 언어인 듯.
'프로그래밍 > 삼성 SWEA' 카테고리의 다른 글
| [SWEA][Python3] 1259. [S/W 문제해결 응용] 7일차 - 금속막대 (0) | 2019.05.29 |
|---|---|
| [SWEA][Python3] 1265. [S/W 문제해결 응용] 9일차 - 달란트2 (0) | 2019.05.29 |
| [SWEA][Python3] 4112. 이상한 피라미드 탐험 (0) | 2019.05.27 |
| [SWEA][Python3] 1798. 범준이의 제주도 여행 계획 (0) | 2019.05.23 |
| [SWEA][Python3] 1248. [S/W 문제해결 응용] 3일차 - 공통조상 (0) | 2019.05.18 |
| [SWEA][Python3] 1245. [S/W 문제해결 응용] 2일차 - 균형점 (1) | 2019.05.17 |
| [SWEA][Python3] 1849. 영준이의 무게측정 (0) | 2019.05.16 |
| [SWEA][Python3] 5357. 터널 속의 기차 (0) | 2019.05.02 |
최근에 달린 댓글 최근에 달린 댓글