[프로그래머스] 리코쳇 로봇 풀이 / Python, JavaScript

프로그래머스

Lv2. 리코쳇 로봇

접근한 방법

이런 유형의 최단 거리 문제는 대부분 BFS로 해결되는데 조건이 조금 특이합니다. 한번 이동 시 벽 또는 장애물이 있을 때까지 계속 들어가야 합니다. 벽이나 장애물을 만나면 그 이전 칸에서 멈춰야 하므로 이 부분에서 이동했던 한칸을 다시 되돌려줘야 합니다. 

 

큐와 방문여부를 담은 배열을 만들어 BFS로 해결합니다. Python은 덱 라이브러리를 사용하면 되고 JavaScript에서는 별도의 라이브러리가 없어 배열로 풀이합니다. 

 

큐에서 row, column 정보를 담은 원소를 꺼내서 한방향씩 순서대로 벽 또는 장애물이 있을 때까지 진입하고 마지막 자리가 방문하지 않은 자리라면 출발한 위치에서의 방문 값 + 1을 넣어주고 해당 자리에서 다시 네 방향을 탐색하기위해 큐에 넣어줍니다.

 

만약 마지막 자리가 목표지점이라면 그대로 현재 위치의 방문값을 리턴합니다.

 

 

작성 코드 (Python)

def solution(board):
    dr = [-1, 1, 0, 0]
    dc = [0, 0, -1, 1]
    
    br, bc = len(board), len(board[0])
    visited = [[0] * bc for _ in range(br)]
    
    def bfs(sr, sc):
        visited[sr][sc] = 1
        
        from collections import deque
        q = deque([(sr, sc)])
        
        while q:
            r, c = q.popleft()
            for i in range(4):
                nr, nc = r, c
                while 1:
                    nr += dr[i]
                    nc += dc[i]
                    if nr < 0 or nc < 0 or nr >= br or nc >= bc:
                        nr -= dr[i]
                        nc -= dc[i]
                        break
                    elif board[nr][nc] == "D":
                        nr -= dr[i]
                        nc -= dc[i]
                        break
                if not visited[nr][nc]:
                    visited[nr][nc] = visited[r][c] + 1
                    q.append((nr, nc))
                if board[nr][nc] == "G":
                    return visited[nr][nc] - 1
        return -1
    
    for i in range(len(board)):
        if "R" in board[i]:
            return bfs(i, board[i].find("R"))

작성 코드 (JavaScript)

function solution(board) {
  const dr = [-1, 1, 0, 0];
  const dc = [0, 0, -1, 1];

  const [br, bc] = [board.length, board[0].length];
  const visited = Array.from({ length: br }, () => Array(bc).fill(0));

  const bfs = (sr, sc) => {
    visited[sr][sc] = 1;
    const q = [[sr, sc]];

    while (q.length) {
      const [r, c] = q.shift();
      for (let i = 0; i < 4; i += 1) {
        let nr = r;
        let nc = c;
        while (1) {
          nr += dr[i];
          nc += dc[i];
          if (nr < 0 || nc < 0 || nr >= br || nc >= bc || board[nr][nc] === "D") {
            nr -= dr[i];
            nc -= dc[i];
            break;
          }
        }
        if (!visited[nr][nc]) {
          visited[nr][nc] = visited[r][c] + 1;
          q.push([nr, nc]);
        }
        if (board[nr][nc] === "G") return visited[nr][nc] - 1;
      }
    }
    return -1;
  };
  for (let i = 0; i < br; i += 1) {
    for (let j = 0; j < bc; j += 1) {
      if (board[i][j] === "R") {
        return bfs(i, j);
      }
    }
  }
}