99클럽 코테 스터디 32/99일차 TIL #리코쳇 로봇(미들러)

문제 출처 : 프로그래머스

문제링크: https://school.programmers.co.kr/learn/courses/30/lessons/169199

from collections import deque

def solution(board):
    # 보드의 크기
    n, m = len(board), len(board[0])
    
    # 시작점과 목표점 찾기
    start = None
    goal = None
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'R':
                start = (i, j)
            elif board[i][j] == 'G':
                goal = (i, j)
    
    # BFS 초기화
    queue = deque([(start[0], start[1], 0)])  # (x, y, 이동 횟수)
    visited = [[False] * m for _ in range(n)]
    visited[start[0]][start[1]] = True
    
    # 네 방향 (상, 하, 좌, 우)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while queue:
        x, y, dist = queue.popleft()
        
        # 목표에 도달한 경우
        if (x, y) == goal:
            return dist
        
        # 네 방향에 대해 이동 시도
        for dx, dy in directions:
            nx, ny = x, y
            
            # 장애물 또는 경계에 닿을 때까지 이동
            while 0 <= nx + dx < n and 0 <= ny + dy < m and board[nx + dx][ny + dy] != 'D':
                nx += dx
                ny += dy
            
            # 이동한 위치가 방문되지 않았을 경우 큐에 추가
            if not visited[nx][ny]:
                visited[nx][ny] = True
                queue.append((nx, ny, dist + 1))
    
    # 목표 지점에 도달하지 못한 경우
    return -1