-
[프로그래머스] 아이템 줍기 - Python3Problem Solving 2023. 2. 24. 15:47
문제
직사각형들의 좌측 하단과 우측 상단의 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배로 만들 생각을 어떻게 하셨는지...
'Problem Solving' 카테고리의 다른 글
[프로그래머스] 이모티콘 할인 행사 - Python3 (2) 2023.02.26 [프로그래머스] 단어 변환 - Python3 (0) 2023.02.24 [프로그래머스] 게임 맵 최단거리 - Python3 (0) 2023.02.23 [프로그래머스] 네트워크 - Python3 (0) 2023.02.22 [프로그래머스] 타겟 넘버 - Python3 (0) 2023.02.20