📗 리코쳇 로봇

프로그래머스

from collections import deque

def solution(board):
    dx, dy = [-1, 1, 0, 0], [0, 0, 1, -1]
    queue = deque()
    
    n = len(board)
    m = len(board[0])
    dist = [[float('inf') for _ in range(m)] for _ in range(n)]
    
    for i in range(n):
        for j in range(m):
            if board[i][j] == 'R':
                queue.append((i, j, 0))
                dist[i][j] = 0
        if queue:
            break
    
    while queue:
        x, y, d = queue.popleft()
        
        if board[x][y] == 'G':
            return d
        
        for i in range(4):
            nx, ny = x, y
            while 0 <= nx+dx[i] < n and 0 <= ny+dy[i] < m and board[nx+dx[i]][ny+dy[i]] != 'D':
                nx += dx[i]
                ny += dy[i]
                
            if dist[nx][ny] > d+1:
                dist[nx][ny] = d+1
                queue.append((nx, ny, d+1))
    
    return -1

• 기본적인 bfs에서 약간의 변형이 요구되었던 문제였습니다.

왜 이렇게 풀었을까?

• 기본 bfs에는 해당 칸이 비어있을 때, 그 칸으로 한 칸씩 전진하는 방식의 알고리즘이었다면,
• 이 문제에서는 게임판 위의 가장자리나 장애물에 부딪힐 때까지 미끄러지는 방식을 구현해야 했습니다.
• 골자는 그대로 가져가되 while문을 한 번 더 추가하여 미끄러짐을 구현하고, 거리를 기록하는 배열을 이용하여 최소 이동 수를 업데이트해줄 수 있었습니다.