[programmers/Lv.2] 리코쳇 로봇

❓  문제

https://school.programmers.co.kr/learn/courses/30/lessons/169199

 

🛎️  아이디어

- 기본 bfs + 끝까지 직진

1. 다음 위치가 범위 안에 있는지, 장애물이 있는 곳인지 확인

2-A. 다음 위치로 이동이 가능하다면 계속 이동 (continue)

2-B. 다음 위치로 이동이 불가능하다면 직전 위치 queue에 append, cost + 1 (break)

 

💻  풀이

from collections import deque

def bfs(board):
  row, col = len(board), len(board[0])

  dx = [-1, 1, 0, 0]
  dy = [0, 0, -1, 1]
  visited = [[False] * col for _ in range(row)]

  queue = deque()

  # 출발점 찾기
  for i in range(row):
    r_index = board[i].find("R")
    if r_index != -1:
      queue.append((i, r_index, 0))
      visited[i][r_index] = True
      break

  while queue:
    x, y, cost = queue.popleft()

    if board[x][y] == "G":
      return cost

    for i in range(4):
      nx, ny = x, y

      while True:
        nx += dx[i]
        ny += dy[i]

        # 계속 갈 수 있으면
        if 0 <= nx < row and 0 <= ny < col and board[nx][ny] != "D":
          continue
        # 갈 수 없으면 바로 직전 자리 append
        else:
          if not visited[nx - dx[i]][ny - dy[i]]:
            queue.append((nx - dx[i], ny - dy[i], cost + 1))
            visited[nx - dx[i]][ny - dy[i]] = True
            break
          else:
            break

  return -1

def solution(board):
  return bfs(board)

print(solution(["...D..R", ".D.G...", "....D.D", "D....D.", "..D...."]))