[프로그래머스] 연습문제(LV2) : 리코쳇 로봇

<문제출처>

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

프로그래머스

 

 

 

접근1. bfs를 탐색을 하면서 최솟값을 갱신해 나간다.

 

 

최종코드

from collections import deque
import sys


def is_range(n, m, x, y):
    return 0 <= x < n and 0 <= y < m


def find(board, x, y, dx, dy, n, m):
    while True:
        nx, ny = x + dx, y + dy
        
        if not is_range(n, m, nx, ny):
            break      
        if board[nx][ny] == "D":
            break
        x, y = nx, ny
    return x, y


def bfs(board, q, dist, n, m):
    dxs, dys = [-1, 0, 1, 0], [0, 1, 0, -1]   

    cnt = 0
    while q:
        x, y = q.popleft()
        
        for dx, dy in zip(dxs, dys):
            # dx, dy 방향으로 갈 수 있는 최대 위치
            nx, ny = find(board, x, y, dx, dy, n, m)
            
            if dist[x][y] + 1 < dist[nx][ny]:
                q.append((nx, ny))
                dist[nx][ny] = dist[x][y] + 1
            
            
def solution(board):
    n, m = len(board), len(board[0])
    INF = sys.maxsize
    
    
    # 시작점, 목표점 찾기
    for i in range(n):
        for j in range(m):
            if board[i][j] == "R":
                sx, sy = i, j
            if board[i][j] == "G":
                tx, ty = i, j
    
    q = deque()
    dist = [[INF]*m for _ in range(n)]
    dist[sx][sy] = 0
    
    q.append((sx, sy))
    bfs(board, q, dist, n, m)
    
    if dist[tx][ty] == INF:
        return -1
    
    return dist[tx][ty]

 

최소 횟수 구하는 문제로 곧바로 bfs로 접근해봤고, 조건이 까다롭지 않은 단순 구현이어서 어렵지않게 통과하였다.