Q22. 블록 이동하기
🐣문제
2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다.
로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다.
로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다.
"0"과 "1"로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.
프로그래머스 링크 | https://programmers.co.kr/learn/courses/30/lessons/60063
🐥풀이
로봇의 크기는 2x1이므로 지도에서 2칸을 차지하고 있다.
로봇을 상하좌우 이동, 또는 회전 시켜 지도의 끝부분까지 도달하는 최소 시간을 구하는 것이므로 BFS를 활용하면 된다.
상하좌우 이동
로봇이 위치하는 두 칸을 각각 상하좌우가 지도 내부이고, 빈칸이라면 이동시킨다. (queue에 삽입)
회전
회전은 로봇이 가로로 놓여져있는지, 세로로 놓여져있는지를 먼저 판단해야 한다.
가로인 경우, 위아래로 회전한다. 즉, 위아래가 지도 내부이고, 벽이 없으면 회전시킨다. (queue에 삽입)
세로인 경우, 좌우로 회전한다. 즉, 좌우가 지도 내부이고, 벽이 없으면 회전시킨다. (queue에 삽입)
queue에서 꺼내고, 삽입하고를 반복하면서 로봇의 위치가 (N,N)에 도달하면 횟수를 출력하고 과정을 종료한다.
단, 로봇이 위치한 곳은 방문 처리한다. (안하면 백방 시간초과..ㅠㅠ)
방문 처리와 queue를 모두 리스트로 처리했으면, 또 시간초과가 뜰거다.. 하..
deque를 이용하자^!^ deque에서 ()와 {}를 적극적으로 활용하자! 시간초과 해결! 우와!~!
🐓코드
from collections import deque
def moving(loc, board):
dist = [[0,1], [0,-1], [-1,0], [1,0]] # 방향
locs = []
r1, r2 = loc
n = len(board)
# 상하좌우 이동
for d in dist:
r1x, r1y, r2x, r2y = r1[0]+d[0], r1[1]+d[1], r2[0]+d[0], r2[1]+d[1]
# 지도 내부이고, 이동할 위치에 벽이 없으면
if 0<=r1x<n and 0<=r1y<n and 0<=r2x<n and 0<=r2y<n and board[r1x][r1y]==0 and board[r2x][r2y]==0:
locs.append({(r1x,r1y), (r2x, r2y)})
# 회전
if r1[0]==r2[0]: # 로봇 가로 배치 (위아래로 회전)
for d in [-1, 1]:
r1x, r2x = r1[0]+d, r2[0]+d
if 0<=r1x<n and 0<=r2x<n and board[r1x][r1[1]]==0 and board[r2x][r2[1]]==0:
locs.append({r1, (r1x, r1[1])})
locs.append({r2, (r2x, r2[1])})
else: # 로봇 세로 배치 (좌우로 회전)
for d in [-1, 1]:
r1y, r2y = r1[1]+d, r2[1]+d
if 0<=r1y<n and 0<=r2y<n and board[r1[0]][r1y]==0 and board[r2[0]][r2y]==0:
locs.append({(r1[0], r1y), r1})
locs.append({(r2[0], r2y), r2})
return locs
def solution(board):
n = len(board) # 지도 크기
queue = deque() # 로봇 위치
queue.append( ( {(0,0), (0,1)}, 0 ) )
visited= [ {(0,0), (0,1)} ]
while queue:
loc, cnt = queue.popleft()
if (n-1, n-1) in loc:
return cnt
for rbt in moving(loc, board):
# 방문 안 한 곳이면
if rbt not in visited:
queue.append((rbt, cnt+1))
visited.append(rbt)
return 0⭐2022.04.26
회전 처리가 굉장히 까다로웠던 문제 ㅠㅅㅠ 회전을 처리했으면 시간초과에서도 또 애먹엇다 뿌앵!! 방문처리 안해서 시간초과 파바박 뜨더니 방문처리 해주면 테스트 케이스 하나가 말썽^^... 나 리스트 러버인데 deque 적극적 활용이 필요해보임 ㅇㅅㅇ!
