리코쳇 로봇
https://school.programmers.co.kr/learn/courses/30/lessons/169199
문제 설명
리코쳇 로봇이라는 보드게임은 격자모양 게임판 위에서 말을 움직이는 게임으로, 시작 위치에서 목표 위치까지 최소 몇 번만에 도달할 수 있는지 말하는 게임입니다.
이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.
다음은 보드게임판을 나타낸 예시입니다.
...D..R
.D.G...
....D.D
D....D.
..D....여기서 "."은 빈 공간을, "R"은 로봇의 처음 위치를, "D"는 장애물의 위치를, "G"는 목표지점을 나타냅니다.
게임판의 상태를 나타내는 문자열 배열 board가 주어졌을 때, 말이 목표위치에 도달하는데 최소 몇 번 이동해야 하는지 return 하는 solution함수를 완성하세요. 만약 목표위치에 도달할 수 없다면 -1을 return 해주세요.
풀이
move()를 통해 각 방향으로 이동하는데 이동 결과 visited가 한 번도 방문한 적 없으면(==-1)이면 위치를 변경한다.
from collections import deque
def solution(board):
row = len(board)
col = len(board[0])
direction = ((1,0), (-1,0), (0,1), (0,-1))
def move(d, x, y):
while True:
x += d[0]
y += d[1]
if x < 0 or y < 0 or x >= row or y >= col : break
if board[x][y] == 'D':break
return x-d[0], y-d[1]
dq = deque()
visited = [[False]*col for _ in board]
for x in range(row):
for y in range(col):
if board[x][y] == "R":
dq.append((x,y,0))
visited[x][y] = True
if board[x][y] == "G":
x_goal, y_goal = x, y
answer = -1
while dq:
x,y,n = dq.popleft()
if x == x_goal and y == y_goal:
answer = n
break
for d in direction:
nx, ny = move(d, x, y)
if visited[nx][ny] == False:
dq.append((nx, ny, n+1))
visited[nx][ny] = True
return answer