문제
문제 설명
로봇개발자 무지는 한 달 앞으로 다가온 카카오배 로봇경진대회에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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으로 주어집니다.
- 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.
코드
from collections import deque
def move_robot(cur_lo1, cur_lo2, figure):
move = []
#위, 아래, 왼쪽, 오른쪽 움직이는 방향을 저장해준다
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]
#로봇을 상하좌우로 움직여보고 움직일 수 있는 위치만 move에 추가해준다
for mv_row, mv_col in direction:
cur1 = (cur_lo1[0] + mv_row, cur_lo1[1] + mv_col)
cur2 = (cur_lo12[0] + mv_row, cur_lo2[1] + mv_col)
if figure[cur1[0]][cur1[1]] == 0 and figure[cur2[0]][cur2[1]] == 0:
move.append((cur1, cur2))
#로봇이 수평 상태일때
if cur_lo1[0] == cur_lo2[0]:
#아래 또는 윗칸에 벽이 없어야 수직 상태로 회전할 수 있다
for i in [-1, 1]:
if figure[cur_lo1[0] + i][cur_lo1[1]] == 0 and figure[cur_lo2[0] + i][cur_lo2[1]] == 0:
move.append((cur_lo1, (cur_lo1[0] + i, cur_lo1[1]))) #cur_lo1을 중심으로 회전했을때 위치
move.append((cur_lo2, (cur_lo2[0] + i, cur_lo2[1]))) #cur_lo2을 중심으로 회전했을때 위치
#로봇이 수직 상태일떄
else:
#왼쪽 또는 오른쪽칸데 벽이 없어야 수평상태로 회전할 수 있다
for i in [-1, 1]:
if figure[cur_lo1[0]][cur_lo1[1] + i] == 0 and figure[cur_lo2[0]][cur_lo2[1] + i] == 0:
move.append(((cur_lo1[0], cur_lo1[1] + i), cur_lo1)) #cur_lo1을 중심으로 회전했을때 위치
move.append(((cur_lo2[0], cur_lo2[1] + i), cur_lo2)) #cur_lo2을 중심으로 회전했을때 위치
return move
def solution(board):
n = len(board)
#외벽까지 표현해주기위해 행,열을 하나씩 추가해준다
figure = [[1] * (n + 2) for _ in range(n + 2)]
for row in range(n):
for col in range(n):
figure[i + 1][j + 1] = board[i][j]
q = deque([(1,1), (1,2), 0]) #로봇이 있는 좌표와 움직인 횟수 저장
check = [((1,1), (1,2))] #전에 갔었던 자리들을 저장
while q:
cur_lo1, cur_lo2, cnt = q.popleft() #현재 로봇이있는 좌표
#로봇이 (n, n)에 있다면 현재까지 움직인 횟수 return
if (n, n) in [cur_lo1, cur_lo2]:
return cnt
#로봇을 이리저리 움직여준다
for cur in move_robot(cur_lo1, cur_lo2, figure):
#로봇이 움직인 위치가 전에 움직였던 위치가 아니라면 추가해준다
if cur not in check:
q.append((*cur, cnt + 1))
check.add(cur)
진행 과정
예제 #1
board = [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]]
1) figure = [[1, 1, 1, 1, 1, 1, 1], [1, 0, 0, 0, 1, 1, 1], [1, 0, 0, 0, 1, 0, 1], [1, 0, 1, 0, 1, 1, 1], [1, 1, 1, 0, 0, 1, 1], [1, 0, 0, 0, 0, 0, 1], [1, 1, 1, 1, 1, 1, 1]] #아래 그림처럼 격자를 생성해준다
2) cur_lo1, cur_lo2, cnt = (1, 1), (1, 2), 0
3) move = [((2, 1), (2, 2)), ((1, 2), (1, 3)), ((1, 1), (2, 1)), ((1, 2), (2, 2))] #로봇을 이리저리 움직여봤을때 움직일 수 있는 위치들
4) q = [((2, 1), (2, 2), 1), ((1, 2), (1, 3), 1), ((1, 1), (2, 1), 1), ((1, 2), (2, 2), 1)] #아직 (n, n)에 도달하지 못함
5) check = {((1, 1), (2, 1)), ((1, 2), (1, 3)), ((2, 1), (2, 2)), ((1, 1), (1, 2)), ((1, 2), (2, 2))} #움직였던 위치 저장
6) cur_lo1, cur_lo2, cnt = (2, 1), (2, 2), 1
7) move = [((1, 1), (1, 2)), ((2, 2), (2, 3)), ((2, 1), (1, 1)), ((2, 2), (1, 2))]
8) q = [((1, 2), (1, 3), 1), ((1, 1), (2, 1), 1), ((1, 2), (2, 2), 1), ((2, 2), (2, 3), 2), ((2, 1), (1, 1), 2), ((2, 2), (1, 2), 2)] #아직 (n, n)에 도달하지 못함
9) check = {((1, 1), (2, 1)), ((1, 2), (1, 3)), ((2, 1), (2, 2)), ((2, 2), (1, 2)), ((2, 2), (2, 3)), ((1, 1), (1, 2)), ((1, 2), (2, 2)), ((2, 1), (1, 1))}
10) cur_lo1, cur_lo2, cnt = (1, 2), (1, 3), 1
11) move = [((2, 2), (2, 3)), ((1, 1), (1, 2)), ((1, 2), (2, 2)), ((1, 3), (2, 3))]
12) q = [((1, 1), (2, 1), 1), ((1, 2), (2, 2), 1), ((2, 2), (2, 3), 2), ((2, 1), (1, 1), 2), ((2, 2), (1, 2), 2), ((1, 3), (2, 3), 2)] #아직 (n, n)에 도달하지 못함
13) check = {((1, 1), (2, 1)), ((1, 2), (1, 3)), ((2, 1), (2, 2)), ((1, 3), (2, 3)), ((2, 2), (1, 2)), ((2, 2), (2, 3)), ((1, 1), (1, 2)), ((1, 2), (2, 2)), ((2, 1), (1, 1))}
14) cur_lo1, cur_lo2, cnt = (1, 1), (2, 1), 1
15) move = [((2, 1), (3, 1)), ((1, 2), (2, 2)), ((1, 2), (1, 1)), ((2, 2), (2, 1))]
16) q = [((1, 2), (2, 2), 1), ((2, 2), (2, 3), 2), ((2, 1), (1, 1), 2), ((2, 2), (1, 2), 2), ((1, 3), (2, 3), 2), ((2, 1), (3, 1), 2), ((1, 2), (1, 1), 2), ((2, 2), (2, 1), 2)] #아직 (n, n)에 도달하지 못함
17) check = {((1, 1), (2, 1)), ((1, 2), (1, 3)), ((2, 1), (2, 2)), ((2, 1), (3, 1)), ((1, 3), (2, 3)), ((2, 2), (1, 2)), ((1, 2), (1, 1)), ((2, 2), (2, 3)), ((2, 2), (2, 1)), ((1, 1), (1, 2)), ((1, 2), (2, 2)), ((2, 1), (1, 1))}
18) cur_lo1, cur_lo2, cnt = (1, 2), (2, 2), 1
19) move = [((1, 1), (2, 1)), ((1, 3), (2, 3)), ((1, 1), (1, 2)), ((2, 1), (2, 2)), ((1, 3), (1, 2)), ((2, 3), (2, 2))]
20) q = [((2, 2), (2, 3), 2), ((2, 1), (1, 1), 2), ((2, 2), (1, 2), 2), ((1, 3), (2, 3), 2), ((2, 1), (3, 1), 2), ((1, 2), (1, 1), 2), ((2, 2), (2, 1), 2), ((1, 3), (1, 2), 2), ((2, 3), (2, 2), 2)] #아직 (n, n)에 도달하지 못함
21) check = {((1, 1), (2, 1)), ((1, 2), (1, 3)), ((1, 3), (1, 2)), ((2, 1), (2, 2)), ((2, 1), (3, 1)), ((1, 3), (2, 3)), ((2, 2), (1, 2)), ((1, 2), (1, 1)), ((2, 2), (2, 3)), ((2, 3), (2, 2)), ((2, 2), (2, 1)), ((1, 1), (1, 2)), ((1, 2), (2, 2)), ((2, 1), (1, 1))}
22) cur_lo1, cur_lo2, cnt = (2, 2), (2, 3), 2
23) move = [((1, 2), (1, 3)), ((2, 1), (2, 2)), ((2, 2), (1, 2)), ((2, 3), (1, 3))]
24) q = [((2, 1), (1, 1), 2), ((2, 2), (1, 2), 2), ((1, 3), (2, 3), 2), ((2, 1), (3, 1), 2), ((1, 2), (1, 1), 2), ((2, 2), (2, 1), 2), ((1, 3), (1, 2), 2), ((2, 3), (2, 2), 2), ((2, 3), (1, 3), 3)] #아직 (n, n)에 도달하지 못함
25) check = {((1, 1), (2, 1)), ((1, 2), (1, 3)), ((1, 3), (1, 2)), ((2, 3), (1, 3)), ((2, 1), (2, 2)), ((2, 1), (3, 1)), ((1, 3), (2, 3)), ((2, 2), (1, 2)), ((1, 2), (1, 1)), ((2, 2), (2, 3)), ((2, 3), (2, 2)), ((2, 2), (2, 1)), ((1, 1), (1, 2)), ((1, 2), (2, 2)), ((2, 1), (1, 1))}
26) cur_lo1, cur_lo2, cnt = (2, 1), (1, 1), 2
27) move = [((3, 1), (2, 1)), ((2, 2), (1, 2)), ((2, 2), (2, 1)), ((1, 2), (1, 1))]
28) q = [((2, 2), (1, 2), 2), ((1, 3), (2, 3), 2), ((2, 1), (3, 1), 2), ((1, 2), (1, 1), 2), ((2, 2), (2, 1), 2), ((1, 3), (1, 2), 2), ((2, 3), (2, 2), 2), ((2, 3), (1, 3), 3), ((3, 1), (2, 1), 3)] #아직 (n, n)에 도달하지 못함
29) check = {((1, 1), (2, 1)), ((1, 2), (1, 3)), ((1, 3), (1, 2)), ((2, 3), (1, 3)), ((2, 1), (2, 2)), ((3, 1), (2, 1)), ((2, 1), (3, 1)), ((1, 3), (2, 3)), ((2, 2), (1, 2)), ((1, 2), (1, 1)), ((2, 2), (2, 3)), ((2, 3), (2, 2)), ((2, 2), (2, 1)), ((1, 1), (1, 2)), ((1, 2), (2, 2)), ((2, 1), (1, 1))}
30) cur_lo1, cur_lo2, cnt = (2, 2), (1, 2), 2
31) move = [((2, 1), (1, 1)), ((2, 3), (1, 3)), ((2, 1), (2, 2)), ((1, 1), (1, 2)), ((2, 3), (2, 2)), ((1, 3), (1, 2))]
32) q = [((1, 3), (2, 3), 2), ((2, 1), (3, 1), 2), ((1, 2), (1, 1), 2), ((2, 2), (2, 1), 2), ((1, 3), (1, 2), 2), ((2, 3), (2, 2), 2), ((2, 3), (1, 3), 3), ((3, 1), (2, 1), 3)]
33) check = {((1, 1), (2, 1)), ((1, 2), (1, 3)), ((1, 3), (1, 2)), ((2, 3), (1, 3)), ((2, 1), (2, 2)), ((3, 1), (2, 1)), ((2, 1), (3, 1)), ((1, 3), (2, 3)), ((2, 2), (1, 2)), ((1, 2), (1, 1)), ((2, 2), (2, 3)), ((2, 3), (2, 2)), ((2, 2), (2, 1)), ((1, 1), (1, 2)), ((1, 2), (2, 2)), ((2, 1), (1, 1))}
34) cur_lo1, cur_lo2, cnt = (1, 3), (2, 3), 2
35) move = [((2, 3), (3, 3)), ((1, 2), (2, 2)), ((1, 2), (1, 3)), ((2, 2), (2, 3))]
36) q = [((2, 1), (3, 1), 2), ((1, 2), (1, 1), 2), ((2, 2), (2, 1), 2), ((1, 3), (1, 2), 2), ((2, 3), (2, 2), 2), ((2, 3), (1, 3), 3), ((3, 1), (2, 1), 3), ((2, 3), (3, 3), 3)] #아직 (n, n)에 도달하지 못함
37) check = {((1, 1), (2, 1)), ((1, 2), (1, 3)), ((2, 3), (3, 3)), ((1, 3), (1, 2)), ((2, 3), (1, 3)), ((2, 1), (2, 2)), ((3, 1), (2, 1)), ((2, 1), (3, 1)), ((1, 3), (2, 3)), ((2, 2), (1, 2)), ((1, 2), (1, 1)), ((2, 2), (2, 3)), ((2, 3), (2, 2)), ((2, 2), (2, 1)), ((1, 1), (1, 2)), ((1, 2), (2, 2)), ((2, 1), (1, 1))}
38) cur_lo1, cur_lo2, cnt = (2, 1), (3, 1), 2
39) move = [((1, 1), (2, 1))]
40) q = [((1, 2), (1, 1), 2), ((2, 2), (2, 1), 2), ((1, 3), (1, 2), 2), ((2, 3), (2, 2), 2), ((2, 3), (1, 3), 3), ((3, 1), (2, 1), 3), ((2, 3), (3, 3), 3)]
41) check = {((1, 1), (2, 1)), ((1, 2), (1, 3)), ((2, 3), (3, 3)), ((1, 3), (1, 2)), ((2, 3), (1, 3)), ((2, 1), (2, 2)), ((3, 1), (2, 1)), ((2, 1), (3, 1)), ((1, 3), (2, 3)), ((2, 2), (1, 2)), ((1, 2), (1, 1)), ((2, 2), (2, 3)), ((2, 3), (2, 2)), ((2, 2), (2, 1)), ((1, 1), (1, 2)), ((1, 2), (2, 2)), ((2, 1), (1, 1))}
42) cur_lo1, cur_lo2, cnt = (1, 2), (1, 1), 2
43) move = [((2, 2), (2, 1)), ((1, 3), (1, 2)), ((1, 2), (2, 2)), ((1, 1), (2, 1))]
44) q = [((2, 2), (2, 1), 2), ((1, 3), (1, 2), 2), ((2, 3), (2, 2), 2), ((2, 3), (1, 3), 3), ((3, 1), (2, 1), 3), ((2, 3), (3, 3), 3)]
45) check = {((1, 1), (2, 1)), ((1, 2), (1, 3)), ((2, 3), (3, 3)), ((1, 3), (1, 2)), ((2, 3), (1, 3)), ((2, 1), (2, 2)), ((3, 1), (2, 1)), ((2, 1), (3, 1)), ((1, 3), (2, 3)), ((2, 2), (1, 2)), ((1, 2), (1, 1)), ((2, 2), (2, 3)), ((2, 3), (2, 2)), ((2, 2), (2, 1)), ((1, 1), (1, 2)), ((1, 2), (2, 2)), ((2, 1), (1, 1))}
......... (너무 많아서 중간 생략...)
cur_lo1, cur_lo2, cnt = (5, 5), (5, 4), 7 #로봇이 (n, n) = (5, 5)에 도달
return 7
'Algorithm & Data Structure > Programmers' 카테고리의 다른 글
| [Programmers]Python_멀리 뛰기 (0) | 2020.12.20 |
|---|---|
| [Programmers]Python_거스름돈 (0) | 2020.12.19 |
| [Programmers]Python_외벽 점검 (0) | 2020.12.17 |
| [Programmers]Python_기둥과 보 설치 (0) | 2020.12.16 |
| [Programmers]Python_베스트앨범 (0) | 2020.12.13 |