로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다.
로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1, 2), (1, 3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2, 1), (2, 2) 두 칸을 차지하게 됩니다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.
로봇은 다음과 같이 조건에 따라 회전이 가능합니다.
위 그림과 같이 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다.
"0"과 "1"로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.
탐색 문제를 제약 조건을 매우 많이 확장한 케이스라고 볼 수 있겠다. BFS를 수행하며 드론의 어떤 부분이라도 목표지점에 도달하면 반환하는 코드를 작성하면 된다.
나는 (x 좌표, y 좌표, 현재 드론이 향한 방향)을 기준으로 생각하고 문제를 풀이하였다. 드론 크기가 1x2이고, 회전이 포함되어있으므로 이를 고려하였다. 주의할 점은, 현재 드론이 향한 방향 기준으로 (드론 반대쪽 x좌표, 드론 반대쪽 y좌표, 반대 방향)은 위와 동일한 경우이니 visited에 저장할 때, 큐에 넣어줄 때 이를 고려해야 한다.
즉 현재 좌표 및 방향에서 다음 이동은 다음 경우의 수가 생긴다.
현재 방향을 유지하며 상하좌우로이동
기준 x, y좌표를 축으로 시계 및 반시계 회전
드론 반대쪽 x, y좌표를 축으로 시계 및 반시계 회전
이 되겠다.
또한 특수한 경우로, 회전 중 좌표가 가리키는 값에 1이 있어선 안된다. 회전 중 지나가는 방향은 (원래 방향 좌표 + 회전 후 방향 좌표)가 된다 (이를테면, [0, 1] 에서 [1, 0] 좌표로 회전한다면 도중에 [0, 1] + [1, 0] = [1, 1] 좌표를 지나치게 된다). 이 역시 고려하며 코드를 짜면 통과할 수 있다.
풀이 코드
from collections import deque
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
MAX = float('inf')
def solution(board):
N = len(board)
answer = 0
visited = set()
q = deque([(0,0,0,0)])
while q :
x, y, r, t = q.popleft()
if (x, y) == (N-1, N-1) or (x + dx[r], y + dy[r]) == (N-1, N-1) :
answer = t
break
if (x, y, r) in visited or (x + dx[r], y + dy[r], (r+2) % 4) in visited :
continue
visited.add((x, y, r))
for i in range(4) :
ax, ay = x + dx[i], y + dy[i]
if not -1 < ax < N or not -1 < ay < N or board[ay][ax] == 1:
continue
_ax, _ay = ax + dx[r], ay + dy[r]
if not -1 < _ax < N or not -1 < _ay < N or board[_ay][_ax] == 1:
continue
q.append((ax, ay, r, t+1))
for i in [-1, 1] :
_r = (r + i) % 4
ax, ay = x + dx[_r], y + dy[_r]
if not -1 < ax < N or not -1 < ay < N or board[ay][ax] == 1:
continue
cx, cy = ax + dx[r], ay + dy[r]
if board[cy][cx] == 1 :
continue
q.append((x, y, _r, t+1))
x, y, r = x + dx[r], y + dy[r], (r+2) % 4
for i in [-1, 1] :
_r = (r + i) % 4
ax, ay = x + dx[_r], y + dy[_r]
if not -1 < ax < N or not -1 < ay < N or board[ay][ax] == 1:
continue
cx, cy = ax + dx[r], ay + dy[r]
if board[cy][cx] == 1 :
continue
q.append((x, y, _r, t+1))
return answer
