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

문제링크 

 

풀이 방법

bfs로 접근하긴 했는데
큐에 넣어야 하는 노드들과 방문 체크해야 하는 노드들을 잘못 생각해서 계속 오답처리가 나더라구요

스터디원님의 풀이 보고 감을 잡아서
다시 풀었습니다!

이전에 풀었던 bfs와 다르게 지나친 모든 노드를 방문 처리 하는게 아니라
끝에 다다른 노드만 방문 처리를 해서 최단 거리를 찾을 수 있었습니다

1. 출발점과 목표점의 좌표를 저장합니다.
2. 시작점을 방문 처리하고 큐에 넣어줍니다.
3. 큐에서 꺼낸 지점부터 상하좌우로 돌면서 한 뱡향으로 갈 수 있는 만큼 끝까지 갈 것
4. 도착한 끝지점을 방문하지 않은 상태면 cnt+1하고 큐에 넣어줌
   (지나가는 모든 노드를 방문처리 하면 안됨!! 왜냐하면 지나갔던 노드들을 다시 지나가야 하는 경우가 존재, 하지만 이미 한 번 방문한 끝지점은 갈 필요가 없기 때문)

 

 

1. 내 풀이

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

  let start;
  let goal;

  const r_length = board.length;
  const c_length = board[0].length;
  const visited = Array.from(new Array(r_length), () =>
    new Array(c_length).fill(false),
  );

  const q = [];

  //1. 출발점과 목표점의 좌표를 저장합니다.
  for (let r = 0; r < r_length; r++) {
    for (let c = 0; c < c_length; c++) {
      if (board[r][c] === 'R') {
        start = [r, c];
      }
      if (board[r][c] === 'G') {
        goal = [r, c];
      }
    }
  }

  //시작점을 방문 처리하고 큐에 넣어줍니다.
  visited[start[0]][start[1]] = true;
  q.push({ current_r: start[0], current_c: start[1], cnt: 0 });

  //큐가 빌 때까지 반복
  while (q.length) {
    const { current_r, current_c, cnt } = q.shift();

    //목표점에 도착하면 리턴
    if (current_r === goal[0] && current_c === goal[1]) {
      return cnt;
    }

    //상하좌우로 돌면서 한 뱡향으로 갈 수 있는 만큼 끝까지 갈 것
    for (let i = 0; i < 4; i++) {
      let next_r = current_r;
      let next_c = current_c;

      //배열의 끝에 다다르거나 방해물이 존재하면 멈춤
      while (
        next_r + dr[i] >= 0 &&
        next_r + dr[i] < r_length &&
        next_c + dc[i] >= 0 &&
        next_c + dc[i] < c_length &&
        board[next_r + dr[i]][next_c + dc[i]] !== 'D'
      ) {
        next_r += dr[i];
        next_c += dc[i];
      }

      //도착한 끝지점을 방문하지 않은 상태면 cnt+1하고 큐에 넣어줌
      if (!visited[next_r][next_c]) {
        visited[next_r][next_c] = true;
        q.push({ current_r: next_r, current_c: next_c, cnt: cnt + 1 });
      }
    }
  }

  return -1;
}

 

bfs에서 방문처리를 어떤 식으로 해야 하는지
새로운 유형을 하나 더 알게 된 것 같아요