아이디어
문제가 원하는 것은 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 구하는 것이다.
또한, 로봇은 (0, 0) ~ (N, N)의 맵 형태에서 움직이므로 BFS를 사용할 수 있겠다.
코드
from collections import deque
def solution(board):
# 로봇 이동
def move(l, r):
possible_pos = [] # 로봇의 다음으로 가능한 위치
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
for i in range(4):
# 단순 이동하기
next_left_wing = (l[0] + dx[i], l[1] + dy[i])
next_right_wing = (r[0] + dx[i], r[1] + dy[i])
# 다음 위치가 벽이 아닐 경우
if new_board[next_left_wing[0]][next_left_wing[1]] == 0 and new_board[next_right_wing[0]][next_right_wing[1]] == 0:
possible_pos.append((next_left_wing, next_right_wing)) # 가능한 위치에 추가
# 회전하기
# 로봇의 날개가 가로 방향일 경우
if l[0] == r[0]:
for d in (-1, 1):
# 벽 존재 여부 확인
if new_board[l[0] + d][l[1]] == 0 and new_board[r[0] + d][r[1]] == 0:
possible_pos.append((l, (l[0] + d, l[1]))) # 오른쪽 날개 회전
possible_pos.append(((r[0] + d, r[1]), r)) # 왼쪽 날개 회전
# 로봇의 날개가 세로 방향일 경우
else:
for d in (-1, 1):
# 벽 존재 여부 확인
if new_board[l[0]][l[1] + d] == 0 and new_board[r[0]][r[1] + d] == 0:
possible_pos.append(((l[0], l[1] + d), l)) # 아래쪽 날개 회전
possible_pos.append(((r[0], r[1] + d), r)) # 위쪽 날개 회전
return possible_pos
def bfs():
q = deque([((1, 1), (1, 2), 0)]) # 왼쪽 날개, 오른쪽 날개, 소요 시간
visited = set([((1, 1), (1, 2))]) # 방문한 좌표
while q:
left_wing, right_wing, time = q.popleft()
if left_wing == (n, n) or right_wing == (n, n): # 어느 한 곳이라도 (n, n)에 도달하면
return time
# 다음으로 가능한 위치들을 확인
for nxt in move(left_wing, right_wing):
if nxt not in visited: # 이미 방문한 위치라면
q.append((*nxt, time + 1))
visited.add(nxt)
n = len(board)
# 이동 판별을 쉽게하기 위해 외벽을 1로 감싸기
new_board = [[1] * (n + 2) for _ in range(n + 2)]
for i in range(n):
for j in range(n):
new_board[i + 1][j + 1] = board[i][j]
cnt = bfs()
return cnt풀이
문제에서 중요한 포인트를 꼽자면 크게 2가지가 있다.
- 로봇의 이동과 회전 처리
- 이동가능한 좌표 판별 처리
로봇의 이동과 회전 처리
로봇의 이동은 일반적으로 사용하는 dx, dy를 선언해서 처리할 수 있다.
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
# 이동하기
for i in range(4):
next_left_wing = (l[0] + dx[i], l[1] + dy[i])
next_right_wing = (r[0] + dx[i], r[1] + dy[i])
# 다음 위치가 벽이 아닐 경우
if new_board[next_left_wing[0]][next_left_wing[1]] == 0 and new_board[next_right_wing[0]][next_right_wing[1]] == 0:
possible_pos.append((next_left_wing, next_right_wing)) # 가능한 위치에 추가이때, 벽이라면 이동하지 못하므로 벽인지 아닌지 판별하는 코드를 추가해야 한다.
로봇의 회전에서는 로봇의 모양을 살펴봐야 한다.
로봇의 가능한 모양은 2가지 이다.
- 가로
- 세로
가로일 때를 살펴보면,
왼쪽으로 90도 회전이 가능하고 오른쪽으로도 90도 회전이 가능하다.
왼쪽으로 회전할 경우, 위쪽으로 왼쪽인지 아래로 왼쪽인지도 구별해야 한다.
- 위쪽으로 왼쪽 회전 : 오른쪽 날개의
(x, y)좌표만 변경되면 된다.x = x - 1,y = y - 1로 변경된다.
- 아래쪽으로 왼쪽 회전 : 오른쪽 날개의
(x, y)좌표만 변경되면 된다.x = x + 1,y = y - 1로 변경된다.
오른쪽으로 회전할 경우에도 마찬가지로 위쪽, 아래쪽인지 구별해야 한다.
로봇의 모양이 세로인 경우에는,
위쪽 날개인지 아래쪽 날개인지만 다르고 나머지는 똑같은 로직이므로 생략.
# 회전하기
# 로봇의 날개가 가로 방향일 경우
if l[0] == r[0]:
for d in (-1, 1):
# 벽 존재 여부 확인
if new_board[l[0] + d][l[1]] == 0 and new_board[r[0] + d][r[1]] == 0:
possible_pos.append((l, (l[0] + d, l[1]))) # 오른쪽 날개 회전
possible_pos.append(((r[0] + d, r[1]), r)) # 왼쪽 날개 회전
# 로봇의 날개가 세로 방향일 경우
else:
for d in (-1, 1):
# 벽 존재 여부 확인
if new_board[l[0]][l[1] + d] == 0 and new_board[r[0]][r[1] + d] == 0:
possible_pos.append(((l[0], l[1] + d), l)) # 아래쪽 날개 회전
possible_pos.append(((r[0], r[1] + d), r)) # 위쪽 날개 회전이동가능한 좌표 판별 처리
문제의 설명에 다음과 같은 조건이 있다.
로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다.
즉, 맵은 1-index 형태이다.
2가지 방식으로 위의 조건을 처리할 수 있다.
- 접근하는 인덱스를
(0, 0) ~ (N - 1, N - 1)로 설정. 1-index에 맞게 맵을 확장
만약, 1번 방식으로 접근하게 된다면 벽 일때를 처리해줘야 할 뿐만 아니라 맵의 바깥인지도 확인해줘야 한다.
그런데, 2번 방식으로 접근한다면 맵을 확장시킬 때, 기존의 벽 바깥은 모두 1로 처리하면 벽 일때만 처리하면 된다.
이때는 행과 열의 크기가 모두 2씩 늘어나므로 다음과 같이 확장시키면 된다.
n = len(board)
# 이동 판별을 쉽게하기 위해 외벽을 1로 감싸기
new_board = [[1] * (n + 2) for _ in range(n + 2)]
for i in range(n):
for j in range(n):
new_board[i + 1][j + 1] = board[i][j]