❓프로그래머스 : 아이템 줍기
〽️ 문제 요약
여러 직사각형이 모두 겹쳐서 좌표 상에 주어질 때 최종적으로 겹쳐진 도형의 테두리가 캐릭터의 이동 경로인 경우, 캐릭터의 위치에서 아이템의 위치까지 가는 가장 짧은 거리를 구하면 되는 문제
🤔 접근법
간단하게 접근했다가 큰 코 다쳤던 문제 (원래 코 크다고 지인들에게 놀림 많이 받음)
우선 맵을 좌표계에 최대 크기(50x50)로 정의하고, 모든 직사각형을 좌표계에 그린다. 단, 맵 상의 빈 공간은 0, 직사각형의 테두리는 1, 직사각형의 내부 공간은 2로 표시하고, 테두리를 그릴 때 이미 다른 직사각형의 내부 공간(2)라면 1로 표시하지 않아야지 최종 겹쳐진 도형의 테두리만 1로 표시가 가능하다.
이제 캐릭터의 위치에서 맵 상으로 1을 따라가며 BFS를 실행해 아이템의 위치에 도달하면 지금까지의 카운트를 반환하는 방법으로 문제를 간단히 해결!… 할 수 있을 줄 알았다.
좌표 상에 사각형을 그릴 때 발생하는 문제가 있는데, 주어지는 특정 두 직사각형의 테두리가 인접해있을 경우(예를 들어, (0, 3) ~ (0, 6), (1, 3) ~ (1, 6)), 논리적으로는 겹쳐져 있지 않고 떨어져 있는 직사각형이지만 우리가 생각하는 좌표 상에는 인접해서 모두 1로 표시될 것이므로 모두 ‘경로’로 인식해버린다.
이를 위해서는 여러가지 방법이 있었다. 직사각형의 중심점을 고려하는 방법 등이 있지만, 위에서 작성한 로직을 최대한 쉽게 수정할 수 있는 방법은 주어진 모든 좌표 스케일을 2배 해버리는 것이다.
맵도 50x50에서 100x100로 정의하고, 주어진 사각형의 좌표, 캐릭터의 좌표, 아이템의 좌표 모두 2배해서 그리면, 위 문제점에서 발생하는 경우의 사각형도 떨어져서 그려질 것이다. 이제 위에서 작성한 로직 그대로 BFS를 실행하면 된다. 이때, 맵을 두 배로 넓혀서 탐색했으므로, 최단 거리가 두 배로 구해지기 때문에 최종 거리를 나누기 2해서 반환해야 한다.
🔡 코드
from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):
characterX *= 2
characterY *= 2
itemX *= 2
itemY *= 2
MAP = [[0 for _ in range(102)] for _ in range(102)]
for r in rectangle:
x1, y1, x2, y2 = map(lambda x : x*2, r)
for y in range(y1, y2+1):
for x in range(x1, x2+1):
if (y == y1 or y == y2 or x == x1 or x == x2) and MAP[y][x] != 2:
MAP[y][x] = 1
else:
MAP[y][x] = 2
queue = deque([(characterY, characterX, 0)])
MAP[characterY][characterX] = 0
dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]
while queue:
y, x, cnt = queue.popleft()
if y == itemY and x == itemX:
return cnt//2
for d in range(4):
ny = y + dy[d]
nx = x + dx[d]
if 0 <= ny < 102 and 0 <= nx < 102 and MAP[ny][nx] == 1 :
queue.append((ny, nx, cnt+1))
MAP[ny][nx] = 0📚 고찰
어떤 로직을 구현한 후 계속해서 예외를 생각해야한다면 기존 로직을 과감하게 버리고 모든 예외 상황을 커버할 수 있는 새로운 로직을 생각해야 한다라는 레퍼런스에서의 고찰이 와닿는 문제였다. 가장 쉬울 것 같은 하나의 로직이 안되면 과감하게 다른 로직을 생각해보자!
