[프로그래머스] Lv.2 리코쳇 로봇 [Python, 파이썬]

• 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/169199
• 🔑 BFS
  • 범위가 끝 또는 'D'를 만날 때까지 이동하는 것만 끝 ✨

 

from collections import deque

def solution(board):
    answer = 0
    start, end = [], []

    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] == 'R':      # 시작점 찾기
                start = [i, j]
            elif board[i][j] == 'G':    # 도착점 찾기
                end = [i, j]

    visit = [[0] * len(board[0]) for _ in range(len(board))]    # 방문 리스트
    visit[start[0]][start[1]] = 1                               # 시작점 체크
    q = deque([start])                                          # 시작점부터 시작
    mx, my = [0, 0, 1, -1], [1, -1, 0, 0]                       # 4방향
    
    while q:
        x, y = q.popleft()
        
        if x == end[0] and y == end[1]:                         # 도착점이면 리턴
            return visit[x][y] - 1
            
        for i in range(4):
            nx, ny = x + mx[i], y + my[i]                       # 다음에 이동할 위치
            while True:                                         # 범위 끝까지 가거나 'D'를 만날 때까지 이동
                if 0 <= nx < len(board) and 0 <= ny < len(board[0]) and board[nx][ny] != 'D':
                    nx += mx[i]
                    ny += my[i]
                else:                                           # 범위 끝이거나 'D'를 만났으면
                    nx -= mx[i]                                 # 바로 전 위치로 이동
                    ny -= my[i]                                 # 바로 전 위치로 이동
                    break
            
            if visit[nx][ny] == 0:                              # 방문 안 했으면
                visit[nx][ny] = visit[x][y] + 1                 # 지금까지 온 횟수를 저장
                q.append([nx, ny])                              # 큐에 위치 저장
    
    return -1