[프로그래머스] lv.2 리코쳇 로봇 python 풀이

풀이

bfs 문제인데, 다음 위치를 큐에 채워주는 부분에서,

장애물을 만나거나 범위 끝까지 도착할때까지 미끄러지는 것을 find_next로 구현하여 다음위치를 찾음.

 

문제

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

 

코드

import collections

def find_next(x,y,tx,ty, board):
    while True:
        nx, ny = x, y

        x += tx
        y += ty

        if not 0<=x<len(board) or not 0<=y<len(board[0]) or board[x][y] == 'D':
            return nx, ny    

def solution(board):
    visited = [[0 for _ in range(len(board[0]))] for _ in range(len(board))]

    for i in range(len(board)):
        for j in range(len(board[0])):
            if board[i][j] == 'R':
                rx, ry = i,j
            if board[i][j] == 'G':
                gx, gy = i,j     

    move = {(-1,0), (0,1), (1,0), (0,-1)}

    q = collections.deque()
    q.append((rx,ry,0))
    visited[rx][ry] = 1

    while q:
        x,y,cnt = q.popleft()

        if x == gx and y == gy:
            return cnt

        for tx,ty in move:
            nx, ny = find_next(x,y,tx,ty,board)

            if 0<=nx<len(board) and 0<=ny<len(board[0]) and board[nx][ny] != 'D' and visited[nx][ny] == 0:
                q.append((nx,ny,cnt+1))
                visited[nx][ny] = 1

    return -1