def solution(board):
"""
Return : 말이 목표에 도달하는데 까지 최소 몇 번 이동해야하는지 / 불가 -1
상하좌우 방향 설정 벽 or 밖에 떨어지기 전까지 계속 이동
이동 횟수 저장 >> visited[i][j]
- 이미 방문한 곳은 이동X
Q >> (cnt, x, y)
"""
from collections import deque
N = len(board)
M = len(board[0])
start_x, start_y = 0, 0
goal_x, goal_y = 0, 0
for i in range(N):
for j in range(M):
if board[i][j] == "R":
start_x, tart_y = i, j
elif board[i][j] == "G":
goal_x, goal_y = i, j
def move(x, y, k):
global visited
cnt = visited[x][y]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
while True:
nx = x + dx[k]
ny = y + dy[k]
if nx < 0 or ny < 0 or nx >= N or ny >= M: break
if board[nx][ny] == "D": break
x, y = nx, ny
if not visited[x][y]:
visited[x][y] = cnt + 1
return x, y
else:
if visited[x][y] > cnt + 1:
visited[x][y] = cnt + 1
return -1, -1
def bfs(x, y):
global visited
Q = deque([(x, y)])
visited = [[0] * M for _ in range(N)]
visited[x][y] = 1
while Q:
x, y = Q.popleft()
for k in range(4):
nx, ny = move(x, y, k)
if nx != -1:
Q.append((nx, ny))
bfs(start_x, tart_y)
# print(visited)
if not visited[goal_x][goal_y]:
return -1
return visited[goal_x][goal_y] - 1
리코쳇로봇