[프로그래머스] 아이템 줍기 - Python3
문제
직사각형들의 좌측 하단과 우측 상단의 x,y가 주어질 때, 전체적인 형태의 테두리를 따라 출발지에서 목표지점으로 가는 최단거리를 구하는 문제
https://school.programmers.co.kr/learn/courses/30/lessons/87694
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
- 알고리즘 분류 - 깊이/너비 우선 탐색(DFS/BFS)
- 난이도 - Level 3
접근 방법
1) 테두리에 해당하는 좌표들 저장
이건 다른 방법이 생각나지 않아 완전탐색을 이용했다.
사각형들의 테두리에 해당하는 좌표들을 하나하나 탐색하며 그 좌표가 다른 사각형 내부에 있다면 테두리가 아닌 것으로 판별하여 쳐내고, 최종적으로 테두리에 해당하는 좌표들을 저장했다.
2) 테두리 BFS
현재 위치를 디큐하고, 현재위치로부터 상하좌우로 한 칸 씩 이동했을 때 이동한 좌표가 테두리에 있다면 인큐하는 것을 반복했다.
이때, 의도하지 않은 최단거리로 가는 것이 골칫거리였다.
예를 들어, 첫 번째 테스트케이스에서 아래 그림의 초록색 화살표처럼, 길이 이어져있지 않음에도 칸 수로는 한 칸 차이기 때문에 의도하지 않은 길로 가게 된다.
이걸 해결하려고 현재 좌표와 다음 좌표의 평균값이 사각형 테두리에 존재할 경우에만 이동하도록 했는데, 이건 딱 이 케이스에만 적용 가능해서 소용 없었다.
가령, 다섯번째 케이스는 (3,5)에서 (3,6)으로 가야하는데, (4,5)로 가도 평균값이 사각형 테두리에 존재하므로 의도하지 않은 최단경로가 된다.
해답은 도형을 두배로 늘리는 것이었다. 상하좌우로 한 칸 이동했을 때 의도치 않은 최단 경로가 발생한다는 점이 문제라면, 겨우 한 칸 이동하는 것으로는 의도치 않은 길로 가는 것은 어림 없도록 길이를 전부 두 배로 늘리는 것이다. 이렇게 하면 위에서 발생한 두 가지 문제는 물론 인접한 좌표로 인한 문제는 모두 해결된다.
[프로그래머스] 아이템 줍기
직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧
velog.io
답안 코드
+10
from collections import deque
def in_rect(rect, x, y): # 좌표가 다른 사각형의 내부에 존재하는지 확인
include = False
for lx2, ly2, rx2, ry2 in rect:
if lx2 < x < rx2 and ly2 < y < ry2:
include = True
break
return include
def make_road(rectangle): # 테두리 좌표 획득
road = []
# 각 사각형 마다
for lx, ly, rx, ry in rectangle:
# 테두리 좌표 하나하나 돌면서
for x in range(lx, rx+1):
y = ly
# 좌표가 다른 사각형에 포함되지 않으면 road에 추가
if not in_rect(rectangle, x, y) and (x,y) not in road:
road.append((x, y))
y = ry
if not in_rect(rectangle, x, y) and (x,y) not in road:
road.append((x, y))
for y in range(ly, ry+1):
x = lx
if not in_rect(rectangle, x, y) and (x,y) not in road:
road.append((x, y))
x = rx
if not in_rect(rectangle, x, y) and (x,y) not in road:
road.append((x, y))
return sorted(road)
def solution(rectangle, characterX, characterY, itemX, itemY):
answer = 50000000
# 두배
for i in range(len(rectangle)):
for j in range(len(rectangle[i])):
rectangle[i][j] *= 2
q = deque()
q.append((characterX*2, characterY*2, 0))
road = make_road(rectangle)
graph = road2graph(road)
vector = [[1,0], [-1,0], [0,-1], [0,1]]
visited = []
while q:
x, y, cnt = q.popleft()
visited.append((x, y))
if x == itemX*2 and y == itemY*2:
answer = min(cnt, answer)
for dx, dy in vector:
if (x+dx, x+dx) in road and (x+dx, x+dx) not in visited:
q.append((x+dx, y+dy, cnt+1))
return answer/2
아이디어 생각하는 것도, 구현하는 것도 오래 걸렸지만 결국 혼자 풀기 실패한 문제..ㅠㅠ 다들 사각형을 2배로 만들 생각을 어떻게 하셨는지...