백준 25558 - 내비게이션 [Python]

https://www.acmicpc.net/problem/25558

25558번: 내비게이션

---

풀이 과정

시작점과 도착점, 그리고 각 내비게이션마다 방문해야 하는 중간점 정보를 담고 있을 때, 중간점을 모두 방문하고 도착점에 도착하는 거리가 가장 짧은, 가장 좋은 내비게이션이 무엇인지 구하는 문제이다.

 

그냥 문제가 시키는대로 구현하면 된다. 각 내비게이션마다 시작점 -> 중간점들 -> 도착점 경로의 맨해튼 거리를 모두 구해주고 그 중 가장 작은 거리를 안내하는 내비게이션의 번호를 출력하면 된다.

---

소스 코드

import sys


def manhatton(a, b, c, d):
    return abs(a-c) + abs(b-d)


N = int(sys.stdin.readline())
sx, sy, ex, ey = map(int, sys.stdin.readline().split())
answer = []
for _ in range(N):
    distance = 0
    now_x, now_y = sx, sy
    Mi = int(sys.stdin.readline())
    for _ in range(Mi):
        next_x, next_y = map(int, sys.stdin.readline().split())
        distance += manhatton(now_x, now_y, next_x, next_y)
        now_x, now_y = next_x, next_y
    distance += manhatton(now_x, now_y, ex, ey)
    answer.append(distance)

answer_index = 0
min_answer = min(answer)

for index, value in enumerate(answer):
    if value == min_answer:
        min_answer = value
        answer_index = index + 1

print(answer_index)