[ PS ] 프로그래머스 LV2 리코쳇 로봇

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

프로그래머스

 

 

이 게임에서 말의 움직임은 상, 하, 좌, 우 4방향 중 하나를 선택해서 게임판 위의 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 칩니다.

문제 조건 중에서 장애물이나 맨 끝에 부딪힐 때까지 미끄러져 이동하는 것을 한 번의 이동으로 계산한다.

BFS 템플릿에서 장애물이나 맨 끝에 부딪힐 때까지 While문으로 직진하는 부분이 응용된 문제이다.

- Javascript

 

const solution = (board) => {
  let answer = 0;
  const dy = [-1, 1,  0, 0];
  const dx = [ 0, 0, -1, 1];
  const R = [];
  const G = [];
  const N = board.length;
  const M = board[0].length;
  const visited = Array.from({length: N}, () => Array(M).fill(false))
  let isPos = false;

  for(let i=0; i<N; i++){
    for(let j=0; j<M; j++){
      if(board[i][j] === 'R') R.push([i, j])
    }
  }

  const BFS = (y, x, c) => {
    const queue = [[y, x, c]];
    visited[y][x] = true;
	
    while(queue.length > 0){
      const [crnt_y, crnt_x, crnt_c] = queue.shift();
    	
      for(let i=0; i<4; i++){
        let [move_y, move_x] = [crnt_y, crnt_x];
        
        // 벽이나 'D'를 만나기 전까지 한 방향으로 쭉 직진
        while(move_y >= 0 && move_y < N && move_x >= 0 && move_x < M && board[move_y][move_x] !== 'D'){
          const next_y = move_y + dy[i]
          const next_x = move_x + dx[i]

		  // 벽일 경우
          if(next_y < 0 || next_y >= N || next_x < 0 || next_x >= M){
          	// 벽을 밟기 전 칸이 목적지인지 확인
            if(board[move_y][move_x] === "G"){
              answer = crnt_c + 1
              isPos = true
              return
            }
            if(!visited[move_y][move_x]){
              visited[move_y][move_x] = true
              queue.push([move_y, move_x, crnt_c+1])
            }
          }else{
            // D일 경우
            if(board[next_y][next_x] === 'D'){
              // D를 밟기 전 칸이 목적지인지 확인
              if(board[move_y][move_x] === "G"){
                answer = crnt_c + 1
                isPos = true
                return
              }
              if(!visited[move_y][move_x]){
                visited[move_y][move_x] = true
                queue.push([move_y, move_x, crnt_c+1])
              }
            }
          }

          [move_y, move_x] = [next_y, next_x]
        }
      }
    }
  }



  BFS(R[0][0], R[0][1], 0)
  if(isPos){
    return answer;
  }
  return -1
}