[Programmers] 리코쳇 로봇(Python, Javascript)

 

문제

요약

상하좌우 방향으로 보드의 끝이나 장애물에 부딪힐 때까지 쭉 가게 하는 것이 한번 이동이다.

R 위치에서 G 위치까지 이동하는 데 필요한 최소 횟수를 구하시오.

 

출처

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

프로그래머스

---

풀이

Python

from collections import deque

def solution(board):
    n, m = len(board), len(board[0])
    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)
    
    d = [(-1,0), (1,0), (0,-1), (0,1)]
    visited = [[-1] * m for _ in range(n)]
    visited[start[0]][start[1]] = 0
    
    q = deque([start])
    
    while q:
        i, j = q.popleft()
        
        if board[i][j] == "G":
            break
        
        for di, dj in d:
            ni, nj = i+di, j+dj
            
            while 0 <= ni < n and 0 <= nj < m and board[ni][nj] != "D":
                ni, nj = ni+di, nj+dj
            
            ni, nj = ni - di, nj - dj
            if visited[ni][nj] == -1:
                visited[ni][nj] = visited[i][j] + 1
                q.append((ni, nj))
    
    return visited[goal[0]][goal[1]]

 

Javascript

function solution(board) {
    const n = board.length;
    const m = board[0].length;
    let sx; let sy;
    let gx; let gy;
    
    for (let i = 0; i<n; i++){
        for (let j = 0; j< m; j++){
            if (board[i][j] == "R"){
                sx = i;
                sy = j;
            } else if (board[i][j] == "G") {
                gx = i;
                gy = j;
            }
        }
    }
    
    visited = Array.from(Array(n), () => new Array(m).fill(-1))
    d = [[-1,0], [1,0], [0,-1], [0,1]]
    visited[sx][sy] = 0;
    q = [[sx, sy]];
    
    while (q.length > 0){
        let [x, y] = q.shift();
        
        if (x == gx && y == gy){
            break;
        }
        
        for (let i = 0; i < 4; i++){
            let nx = x + d[i][0];
            let ny = y + d[i][1];
            
            while (0 <= nx && nx < n && 0 <= ny && ny < m && board[nx][ny] != "D") {
                nx += d[i][0];
                ny += d[i][1];
            }
            
            nx -= d[i][0];
            ny -= d[i][1];
            
            if (visited[nx][ny] == -1){
                q.push([nx, ny]);
                visited[nx][ny] = visited[x][y] + 1;
            }
        }
    }
    return visited[gx][gy];
}