아이템 줍기

• 그냥 구현 문제. 사각형의 최대 갯수와 좌표의 범위가 모두 작아서 어떤식으로 구현하든 통과되는데에는 문제가 없다.
• 여기에서는 그냥 둘레를 따라서 1칸씩 이동하면서 한바퀴 돌면서, 전체 둘레 길이와 아이템까지의 거리를 재는 방식으로 구현했다
  • 만약에 조금 더 효율적으로 구현해야만 했다면, 이동 방향이 바뀌는 점인 사각형의 꼭지점들과 사각형간의 교점들만 미리 구해서, 같은 방향으로는 한번에 이동시키는 방식으로 했을것이다. 이분탐색이나 세그트리 등을 이용하면 이동할 다음 목적지 좌표를 찾는것도 좀더 빠르게 할수 있을 것 같다
• 그냥 둘레를 따라서 1칸씩 이동할때에는, 전후좌후 4방향의 좌표 중에서 둘레 위의 점을 찾아서 그리로 이동하는 식으로 구현할 것이다. 이 때에도 어떤 점이 둘레 위의 점인지를 확인하는 방법을 다르게 구현할수 있을 텐데, 하나는 매번 주어진 사각형들의 비교해서 O(n)에 처리하는 것이고, 다른 방법은 처음에 미리 2차원 배열에 둘레의 점들을 다 구해 놓고서 O(1)에 확인하는 것이다. 둘레의 길이가 O((x+y)*n) 이니까.. 전자로 처리하면 총 시간복잡도가 O((x+y)*n^2) 이 될것이고, 후자로 처리하면 전처리와 탐색이 모두 O((x+y)*n)이니까 총 O((x+y)*n)에 가능하다.
  • 실제 구현은 전자의 방식으로 했다.

"""Solution code for "Programmers 87694. 아이템 줍기".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/87694
- Solution link: http://www.teferi.net/ps/problems/programmers/87694
"""

import itertools


def is_movable(cur_x, cur_y, next_x, next_y, rectangles):
    x, y = (cur_x + next_x) / 2, (cur_y + next_y) / 2
    is_on_any_border = any(
        (x in (x1, x2) and y1 <= y <= y2) or (y in (y1, y2) and x1 <= x <= x2)
        for x1, y1, x2, y2 in rectangles)
    is_inside_any_rect = any(
        x1 < x < x2 and y1 < y < y2 for x1, y1, x2, y2 in rectangles)
    return is_on_any_border and not is_inside_any_rect


def solution(rectangle, characterX, characterY, itemX, itemY):
    cur_pos = (characterX, characterY)
    prev_pos = None
    for dist in itertools.count():
        if cur_pos == (characterX, characterY) and prev_pos:
            perimeter = dist
            break
        elif cur_pos == (itemX, itemY):
            dist_to_item = dist
        for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            next_pos = (cur_pos[0] + dx, cur_pos[1] + dy)
            if next_pos != prev_pos and is_movable(*cur_pos, *next_pos,
                                                   rectangle):
                prev_pos, cur_pos = cur_pos, next_pos
                break
    return min(dist_to_item, perimeter - dist_to_item)