문제
로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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 함수를 완성해주세요.
제한 사항
board의 한 변의 길이는 5 이상 100 이하입니다.
board의 원소는 0 또는 1입니다.
로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.
입출력 예
입출력 예에 대한 설명
문제에 주어진 예시와 같습니다.
로봇이 오른쪽으로 한 칸 이동 후, (1, 3) 칸을 축으로 반시계 방향으로 90도 회전합니다. 다시, 아래쪽으로 3칸 이동하면 로봇은 (4, 3), (5, 3) 두 칸을 차지하게 됩니다. 이제 (5, 3)을 축으로 시계 방향으로 90도 회전 후, 오른쪽으로 한 칸 이동하면 (N, N)에 도착합니다. 따라서 목적지에 도달하기까지 최소 7초가 걸립니다.
문제 해결
사실 문제를 보자마자, '아 이래서 카카오 문제가 어렵다고 하는구나..'라는 생각을 하면서 동시에 은근 할 수 있다고 생각했다. 뭔가 회전하는 부분만 잘 해결하면 쉽게 풀 수 있을 것이라고 생각했다.
나는 처음에는 하나의 칸과 방향을 저장을 해서 해결할 수 있다고 생각했다.
그렇게 하면 사실 조건을 거쳐야하는 부분이 너무 많아서 다른 방법을 찾았다.
그래서 두 칸과 방향을 모두 저장을 해서 시작을 하려 했지만 회전하는 방법을 해결하지 못해서 블로그를 찾아봤다.
차지하는 두 칸과 방향을 모두 저장을 하는 방식은 똑같았다.
사실 내가 경이로웠던 부분은 우리가 왼쪽으로 90도, 오른쪽으로 90도 회전을 시킬텐데 방향 벡터를 순서대로 넣어 방향 벡터 리스트의 인덱스에 따라 관리하는 부분에서 정말 대단한 코드라고 생각했다.
그리고 두 번째로 내가 생각하지 못했던 부분은 같은 위치지만 표현 방식에 따라 다를수도 있다는 점 이었다. 왜냐하면 회전하는 축이 달라지기 때문이다. 무슨 말이냐 하면 아래 그림을 보자
위 로봇은 (0, 0)과 (0, 1)을 차지하고 있고 방향은 오른쪽이다.
그런데 코드 상에서는 (0, 1) (0, 0)과 방향이 왼쪽으로 표기될 수도 있다는 말이다.
그런데 이것은 다른 로봇이라고 인식해야한다. 왜냐하면 아까 말했듯이 회전하는 축이 (0,0)이 되냐, (0,1)이 되냐의 차이기 때문이다.
그래서 두 경우를 모두 체크를 해야 한다.
최종 코드
from collections import deque
# 방향 벡터 (우, 하, 좌, 상)
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
MAX = float('inf')
def solution(board):
N = len(board) # 보드 크기 (N x N)
answer = 0
visited = set() # 방문한 상태 저장
# 큐에 초기 상태 추가: (x, y, r, t)
# (x,y) : 로봇의 첫 번째 칸 위치
# r : 두 번째 칸이 첫 번째 칸에서 어떤 방향에 있는지 (0=우,1=하,2=좌,3=상)
# t : 현재까지 걸린 시간
q = deque([(0,0,0,0)])
while q:
x, y, r, t = q.popleft()
# 로봇의 두 칸 중 하나라도 도착지 (N-1, N-1)에 도달하면 성공
if (x, y) == (N-1, N-1) or (x + dx[r], y + dy[r]) == (N-1, N-1):
answer = t
break
# 이미 방문한 상태인지 확인
# (x,y,r) = (첫 번째 칸이 (x,y), 방향 r)
# (x+dx[r], y+dy[r], (r+2)%4) = 같은 배치를 반대로 표현한 상태
if (x, y, r) in visited or (x + dx[r], y + dy[r], (r+2) % 4) in visited:
continue
visited.add((x, y, r)) # 방문 체크
# -------------------------------
# 1. 로봇을 상하좌우로 "평행 이동"하는 경우
# -------------------------------
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))
# -------------------------------
# 2. (x,y)를 축으로 삼아 "회전"하는 경우
# -------------------------------
for i in [-1, 1]: # 왼쪽(-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 not (0 <= cx < N and 0 <= cy < N) or board[cy][cx] == 1:
continue
q.append((x, y, _r, t+1)) # 회전 성공 시 큐에 추가
# -------------------------------
# 3. 다른 칸을 축으로 삼아 "회전"하는 경우
# -------------------------------
# 기준점을 (x+dx[r], y+dy[r])로 바꾸고 방향을 반대로 뒤집음
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 not (0 <= cx < N and 0 <= cy < N) or board[cy][cx] == 1:
continue
q.append((x, y, _r, t+1))
return answer