문제 설명 및 제한사항
아이디어 및 해결 방법
코드
from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):
# 테두리의 격자점을 나타내는 그래프 (혹은 2차원 배열)을 만든 뒤 BFS.
#
# 주의해야할 점을 설명하기 위해 입출력 예 #1에서 예를 들면,
# (3, 5)과 (3, 6)은 모두 테두리 격자점이지만 (3, 5)에서 (3, 6)으로
# 바로 갈 수는 없다. 하지만 단순한 2차원 배열 상에서 격자점을 1로 표현
# 한다면 (3,5)=1, (3,6)=1로 BFS 탐색 순서 상 (3,5)에서 (3,6)으로 바로
# 가는 방식으로 잘못 동작하게 된다. 이를 방지하기 위해 격자점이 아니라 0.5 단위의
# 2차원 배열을 구성한다. (max 1000 x 1000)
A = [[0 for _ in range(1020)] for _ in range(1010)]
for x1, y1, x2, y2 in rectangle:
# 우선 직사각형 내부의 모든 점을 다 1로 칠한 뒤
for r in range(2*x1, 2*x2 + 1):
for c in range(2*y1, 2*y2 + 1):
A[r][c] = 1
for x1, y1, x2, y2 in rectangle:
# 각 꼭지점을 0.5만큼 내부로 이동시킨 작은 직사각형 내부의 점을 0으로 복구한다.
# 이러면 테두리의 점만 남길 수 있음.
for r in range(2*x1 + 1, 2*x2):
for c in range(2*y1 + 1, 2*y2):
A[r][c] = 0
# BFS
visited = set()
q = deque()
q.append((2*characterX, 2*characterY, 0))
visited.add( (2*characterX, 2*characterY) )
while len(q) > 0:
r, c, d = q.popleft()
if r == 2*itemX and c == 2*itemY:
return d
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
if (r+dr, c+dc) not in visited and A[r+dr][c+dc] == 1:
q.append( (r+dr, c+dc, d+0.5) )
visited.add( (r+dr, c+dc) )
Python
복사
출처
프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges