Programmers - 아이템 줍기

문제 링크

가로,세로의 길이가 2이상인 경우는 확실하게 방문 불가능한 지점(사각형 내부)을 체크할 수 있는데,
가로의 길이가 1이거나 세로의 길이가 1인 경우에는 방문 불가능한 지점을 체크하기 까다로워 문제 예시 중 5번 케이스를 풀지 못했었다.

아무리 생각해도 풀이방법이 떠오르지 않아 질문하기를 봤는데 아예 사각형의 길이를 2배씩 늘려버리는 방법으로 문제를 푼 사람들이 많았다.

이 방법으로 별다른 로직 수정 없이 바로 풀 수 있었는데, 이런 생각은 어떻게 하는걸까?

from collections import deque


def solution(rectangle, characterX, characterY, itemX, itemY):
    N = 101
    # 도형 안쪽이라 방문 불가능한 경우
    inner = [[False for _ in range(N+1)] for __ in range(N+1)]
    # 해당 좌표에서 위로 이동 가능한지
    u = [[False for _ in range(N+1)] for __ in range(N+1)]
    # 해당 좌표에서 오른쪽으로 이동 가능한지
    r = [[False for _ in range(N+1)] for __ in range(N+1)]

    def add_edge(ax, ay, bx, by):
        for i in range(ax, bx):
            r[i][ay] = r[i][by] = True
        for i in range(ay, by):
            u[ax][i] = u[bx][i] = True

    def check_inner(ax, ay, bx, by):
        for i in range(ax+1, bx):
            for j in range(ay+1, by):
                inner[i][j] = True

    # 가로,세로 길이가 1인 사각형은 inner 처리가 까다로움
    # 모든 입력을 2배로 늘린다
    rectangle = list(
        map(lambda x: (x[0]*2, x[1]*2, x[2]*2, x[3]*2), rectangle))
    characterX *= 2
    characterY *= 2
    itemX *= 2
    itemY *= 2

    for (ax, ay, bx, by) in rectangle:
        add_edge(ax, ay, bx, by)
        check_inner(ax, ay, bx, by)

    q = deque()
    count = 0
    visit = [[False for _ in range(N+1)] for __ in range(N+1)]
    moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    q.append((characterX, characterY))
    visit[characterX][characterY] = True

    def can_move(x, y, dx, dy):
        # 이미 방문한 경우
        if visit[x+dx][y+dy] == True:
            return False
        # 정사각형 내부인 경우
        if inner[x+dx][y+dy] == True:
            return False

        # 길이 있는지 확인
        if dx == 1:
            return r[x][y]
        if dx == -1:
            return r[x-1][y]
        if dy == 1:
            return u[x][y]
        if dy == -1:
            return u[x][y-1]

    while len(q) > 0:
        for _ in range(len(q)):
            (x, y) = q.popleft()
            if (x, y) == (itemX, itemY):
                return count//2

            for (dx, dy) in moves:
                if can_move(x, y, dx, dy):
                    ax = x+dx
                    ay = y+dy
                    visit[ax][ay] = True
                    q.append((ax, ay))

        count += 1

    return 0