[코딩테스트/Python] 프로그래머스 "아이템 줍기"

📍 문제 출처

https://school.programmers.co.kr/learn/courses/30/lessons/87694

프로그래머스

 

📍 풀이 방법

• 최대 4개의 직사각형으로 이루어진 다각형의 둘레를 따라 탐색하는 문제이다.
• 좌표 공간이 크지 않고 (50⨉50) 직사각형의 개수가 제한되어 있어 (≤ 4) 단순하게 구현하면 된다고 한다.
• 처음에는 bool 형태의 2차원 배열에 직사각형의 둘레를 모두 표시해두려고 했다. 그러나 다음과 같이 두 개의 직사각형이 1 차이로 위치할 경우 둘레가 아닌데 둘레로 인식되는 문제가 있었다.

직사각형의 둘레가 아닌데 둘레로 인식되는 경우

• 다각형의 둘레는 다른 직사각형에 포함되지 않는, 직사각형의 둘레이다.
• 위의 정의에 따라 (1) 직사각형의 둘레인지, (2) 다른 직사각형에 포함되지 않는지 검증하여 다각형의 둘레만을 인식하였다.
• 해결한 후 다른 풀이를 참고하여 코드를 리팩토링했다. 앞서 언급한 반례를 검증하기 위해 좌표 공간을 2배로 늘리거나, 변의 중점을 이용하는 것이 주된 풀이이다.

def is_border(rectangles, x1, y1, x2, y2):
    x, y = (x1 + x2) / 2, (y1 + y2) / 2
    is_rect_border = any(
        (x in {rx1, rx2} and ry1 <= y <= ry2) or (y in {ry1, ry2} and rx1 <= x <= rx2)
        for rx1, ry1, rx2, ry2 in rectangles
    )
    is_inside_rect = any(
        rx1 < x < rx2 and ry1 < y < ry2 for rx1, ry1, rx2, ry2 in rectangles
    )
    return is_rect_border and not is_inside_rect

def solution(rectangles, char_x, char_y, item_x, item_y):
    N = M = 50
    
    # (1, 1) ~ (N, M) 좌표를 (0, 0) ~ (N - 1, M - 1) 좌표로 조정함
    rectangles = [
        [rx1 - 1, ry1 - 1, rx2 - 1, ry2 - 1] for rx1, ry1, rx2, ry2 in rectangles
    ]
    char_x, char_y = char_x - 1, char_y - 1
    item_x, item_y = item_x - 1, item_y - 1
    
    # 다각형 둘레를 따라 돌면서 아이템까지의 거리와 다각형 둘레를 구함
    x, y = char_x, char_y
    px = py = None
    dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
    item_dist, total_dist = 0, 0
    while (x, y) != (char_x, char_y) or (px, py) == (None, None):
        if (x, y) == (item_x, item_y):
            item_dist = total_dist
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if 0 <= nx < N and 0 <= ny < M and (nx, ny) != (px, py):
                if is_border(rectangles, x, y, nx, ny):
                    px, py = x, y
                    x, y = nx, ny
                    break
        total_dist += 1
    answer = min(item_dist, total_dist - item_dist)
    return answer

 

📍 참고 자료

https://www.teferi.net/ps/problems/programmers/87694

아이템 줍기 [테페리넷]