Baekjoon 31885. Yunny's Trip / Python

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

알고리즘 설명

문제 설명

회윤이는 특정 목적지 (Ex, Ey)로 이동해야 한다.
이동하는 방법은 두 가지가 있다.

1. 인접한 격자판으로 한 칸 이동한다. -> 기력 1 소모
2. 아이템을 사용하여 (a, b) 만큼 이동한다. -> 기력 2 소모

조건

1. 초기 기력 K로 목적지에 도달할 수 있는지 확인한다.
2. 도달 가능하다면 최소 기력을 구한다.
3. 기력은 0 이상으로 유지해야 한다.

코드 설명

1. 초기 거리 계산 : 목적지로 아이템 없이 직접 이동하는 경우의 거리를 계산한다.
2. 아이템의 좌표와 목적지의 상대 좌표를 활용하여, 코드를 최대한 단축시킨다. : 시간 복잡도를 N으로 나누는 효과를 얻을 수 있다.
3. 도달 가능한 경우의 최소 소모 기력을 계산한다.

import sys; input = sys.stdin.readline

n, k = map(int, input().split()) # 아이템 개수, 초기 기력
items = [tuple(map(int, input().split())) for _ in range(n)] # 아이템 좌표들
goal_x, goal_y = map(int, input().split()) # 목적지 좌표

# 초기값 설정
res = abs(goal_x) + abs(goal_y) # 목적지까지 직접 이동하는 경우의 기력 소모

# 목적지와 각 아이템 좌표의 상대 좌표 계산을 위한 집합
res_set = set()

# 아이템 좌표로부터 목적지의 상대 좌표 계산
for x, y in items:
    res_set.add((goal_x - x, goal_y - y))

# 아이템 사용과 이동을 고려한 최소 기력 소모 계산
for x, y in items:
    res = min(res, abs(goal_x - x) + abs(goal_y - y) + 2) # 아이템 사용시 기력 소모
    if (x, y) in res_set: 
        res = min(res, 4) # 아이템 사용 후 동일 좌표에 다른 아이템 도달 가능시 최소 기력 소모
    # 인접한 칸으로 이동하는 경우를 고려한 기력 소모
    for dx, dy in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
        if (x + dx, y + dy) in res_set:
            res = min(res, 5)

# 최종 기력 소모가 초기 기력 k 이내인 경우 출력, 그렇지 않으면 -1 출력
print(res if res <= k else -1)