아이템 줍기
시간 제한: 10초
학습 키워드: DFS, 구현
문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/87694
문제 설명
지형을 나타내는 직사각형이 담긴 2차원 배열 rectangle, 초기 캐릭터의 위치 characterX, characterY, 아이템의 위치 itemX, itemY가 solution 함수의 매개변수로 주어질 때, 캐릭터가 아이템을 줍기 위해 이동해야 하는 가장 짧은 거리를 return 하도록 solution 함수를 완성해주세요.
제한사항
rectangle의 세로(행) 길이는 1 이상 4 이하입니다.
rectangle의 원소는 각 직사각형의 [좌측 하단 x, 좌측 하단 y, 우측 상단 x, 우측 상단 y] 좌표 형태입니다.
직사각형을 나타내는 모든 좌표값은 1 이상 50 이하인 자연수입니다.
서로 다른 두 직사각형의 x축 좌표, 혹은 y축 좌표가 같은 경우는 없습니다.
(생략)
문제 풀이
코드 설명
from collections import deque
def solution(rectangle, characterX, characterY, itemX, itemY):
arr = [[-1 for _ in range(102)] for _ in range(102)]
for rect in rectangle:
x1,y1,x2,y2 = map(lambda x: x*2,rect)
for x in range(x1,x2+1):
for y in range(y1,y2+1):
if x1<x<x2 and y1<y<y2:
arr[x][y]=0
elif arr[x][y]!=0:
arr[x][y]=1
def bfs():
queue = deque()
visited = [[False for _ in range(102)] for _ in range(102)]
dx=[-1,0,1,0]
dy=[0,1,0,-1]
stx,sty=characterX*2,characterY*2
visited[stx][sty] = True
queue.append([stx,sty,0])
while queue:
x,y,dist = queue.popleft()
if x==2*itemX and y==2*itemY:
return dist//2
for i in range(4):
nx,ny = x+dx[i],y+dy[i]
if arr[nx][ny] == 1 and not visited[nx][ny]:
queue.append([nx,ny,dist+1])
visited[nx][ny]=True
return bfs()
코드 참고 : (https://jyeonnyang2.tistory.com/247)
코멘트
dfs,bfs 문제지만 구현의 아이디어가 중요했던 문제. 지날 수 있는 부분을 1로 해서 bfs로 풀고자 했지만 꺾이는 부분 처리에 곤란함을 겪었었다. 단순한 전처리 없이 꺾이는 부분을 통과하고자 하면 모서리를 따라 가는게 아니라 도형을 관통해서 지나가기 때문이다. 한 칸을 배열로 했을 때 도형의 모서리를 정의하기 힘들어서 생긴 문제. 따라서, 모서리 처리를 어떻게 해야할까 고민을 했고 결국 스스로 할당한 시간을 초과해서 다른 분의 풀이를 참고했다. 빨리 참고하길 잘했다(..) 모서리를 표현하기 어렵기 때문에 모서리를 정의하고자 모든 것을 2배로 만든 것. 이런 아이디어 부분은 한 번 인사이트를 깨닫는게 중요하다고 생각하기 때문에 최대한 다른 사람의 풀이를 찾아보고 어디에 적용할지 생각해보는게 중요하다고 다시금 생각한다.
