[프로그래머스] 리코쳇 로봇 - 자바스크립트

 

문제

프로그래머스

 

---

코드

function solution(board) {
  const row = board.length;
  const col = board[0].length;
  const [dx, dy] = [
    [-1, 0, 1, 0],
    [0, 1, 0, -1],
  ];
  const NON_DIR = -10;
  const movedMap = {};
  const BLOCK = {
    empty: '.',
    start: 'R',
    obstacle: 'D',
    goal: 'G',
  };

  function getStartPos(board) {
    for (let i = 0; i < row; i++) {
      for (let j = 0; j < col; j++) {
        if (board[i][j] === BLOCK.start) return [i, j];
      }
    }
  }

  function endOfBoard(x, y) {
    if (x < 0 || x >= row || y < 0 || y >= col) return true;
    if (board[x][y] === BLOCK.obstacle) return true;
    return false;
  }

  function getReverseDir(dir) {
    return (dir + 2) % 4;
  }

  function checkGoal(x, y) {
    return board[x][y] === BLOCK.goal;
  }

  const startPos = getStartPos(board);
  board[startPos[0]][startPos[1]] = BLOCK.empty;

  function bfs() {
    const arr = [[...startPos, NON_DIR, 0]];
    let idx = 0;

    while (1) {
      if (arr.length - 1 < idx) return;

      const [x, y, dir, cnt] = arr[idx++];
      const movedPath = `${x}/${y}/${dir}`;
      if (movedMap[movedPath]) continue;
      movedMap[movedPath] = true;

      for (let i = 0; i < 4; i++) {
        let [nx, ny] = [x + dx[i], y + dy[i]];

        if (dir !== NON_DIR) {
          if (dir === i) continue;
          if (getReverseDir(dir) === i) continue;
        }
        if (endOfBoard(nx, ny)) continue;

        while (!endOfBoard(nx + dx[i], ny + dy[i])) {
          [nx, ny] = [nx + dx[i], ny + dy[i]];
        }

        if (checkGoal(nx, ny)) return cnt + 1;
        arr.push([nx, ny, i, cnt + 1]);
      }
    }
  }

  return bfs() ?? -1;
}

 

---

풀이

문제 조건

리코쳇 로봇

격자모양 게임판 위에서 말을 움직이는 게임.

시작 -> 목표까지 최소 도달수를 구해야 한다.

 

상하좌우로 움직이며 장애물/맨끝에 부딪힐 때 까지 미끄러지는게 1번의 이동이다.

게임판에서 .은 빈공간, R은 처음 위치, D는 장애물, G는 목표지점

게임판 행렬 board가 주어졌을 때, 최소 몇번 이동해야하는지 구하자.

목표위치에 도달 불가능하다면 -1 을 반환한다.

 

제한사항

3<=board.length<=100

3<=board element <= 100

board element(string)의 크기 동일

이동방법 : 상하좌우

 

풀이방향

코드가 굉장히 난잡해졌음을 고려하면, 더 좋은 풀이방법이 있을 것 같다.

이렇게도 무식하게 풀 수 있구나 정도만 참고하기를 바란다. ^^;

 

필자가 생각한 풀이 시나리오는 다음과 같다.

1. 끝까지 미끄러져야 하므로 이동방향이 빈공간(.)이거나 목표지점(G)이라면 계속 이동한다.

2. 더이상 이동할 수 없을 때 현재 위치를 파악한다. 현재 위치가 G이면 정답이다.

3. 다음 이동을 정할 때 미끄러진 방향과 미끄러진 반대방향을 제외한 2가지 방향중 선택한다.

4. 다시 1번으로 돌아가 이동방향으로 미끄러져 나간다.

 

우선 가장 짧게 도착한 경우에 바로 끝내기 위해 bfs로 접근하기로 했다.

자바스크립트로 bfs를 활용할 때 주의할 점은 제대로 동작할 큐를 구현해야 한다.

아니면 배열에 다음 좌표를 쌓아가면서 인덱스를 변경시키는 방법을 쓰는게 좋아보인다.

레벨2짜리 문제에 큐를 구현해 넣기엔 민망해서, 배열 인덱스 방법을 활용하기로 했다.

 

문제에는 "도달할 수 없는 경우"라는 변수가 있다.

도달할 수 없는 경우 탈출을 위해 2가지 탈출방법을 떠올렸다.

 

1) 최대 미끄러지는 횟수를 정해보자.

board가 100x100이므로 어느정도 반복했다면 이미 지나온 길을 반복하고 있을 것이다.

놀라운 예지력으로 100만~1000만정도의 반복수를 정해보면 되지 않을까?

 

2) memoizatoin을 활용한다.

만약 "(1,2) 좌표에서 왼쪽방향으로 이동" 이라는 정보를 기록해두었다고 가정하자.

이 정보가 한번 더 출현한 경우라면 더이상 미끄러져야할 이유가 없는 경우다.

이 경우에는 더이상 상하좌우의 탐색을 진행하지 말고 다음 큐의 원소로 이동하는 것이다.

 

1번 케이스로 찍신이 되는 방법도 좋지만, 2번이 조금 더 합리적으로 보이니 2번으로 탈출조건을 설정해보자.

 

요약하면 다음과 같다.

가장 짧은 경로를 구하기 위해 bfs를 활용해보자.

단 Array.prototype.shift를 쓰기보다는 배열에 쌓인 순서대로 idx를 1씩 증가시키며 검증하자.

이동방향대로 미끄러 질 때는 루프를 돌아준다. board의 끝이거나, 장애물(D)일 때 현 위치에서 멈춘다.

현 위치에서 목표지점인지 검증한다. 목표지점이 아니라면, 큐(배열)에 [현재 좌표, 이동했던 방향, 이동횟수] 를 넣어준다.

도달할 수 없는 경우를 검출하기 위해 "현재좌표/이동방향" 정보를 기록한다. 이 정보가 반복되는 경우는 더이상 미끄러질 필요가 없다.

 

bfs의 결과가 나왔다면 그대로 출력하면 되고, 결과가 나오지 않았다면 -1을 반환하면 된다.

 

이 의식의 흐름대로 코드를 다시 이해해보자.

 

---

주석 첨부 코드

function solution(board) {
  const row = board.length;
  const col = board[0].length;
  const [dx, dy] = [
    [-1, 0, 1, 0],
    [0, 1, 0, -1],
  ]; // 이동방향에 따른 상하좌우 이동크기 dx,dy
  const NON_DIR = -10; // 맨 처음 시작점에선 방향이 없다.
  const movedMap = {}; // 좌표,이동방향을 기록할 memoization Map이다.
  const BLOCK = {
    empty: '.',
    start: 'R',
    obstacle: 'D',
    goal: 'G',
  }; // 상수 값은 모아두면 좋다.

  function getStartPos(board) {
    for (let i = 0; i < row; i++) {
      for (let j = 0; j < col; j++) {
        if (board[i][j] === BLOCK.start) return [i, j];
      } // 시작지점을 찾는 함수.
    }
  }

  function endOfBoard(x, y) {
    if (x < 0 || x >= row || y < 0 || y >= col) return true;
    if (board[x][y] === BLOCK.obstacle) return true;
    return false;
  } // 다음 이동할 위치가 board의 끝이거나, 장애물인지 판단하는 함수.

  function getReverseDir(dir) {
    return (dir + 2) % 4;
  } // 현재 진행방향과 반대방향의 dir를 반환하는 함수.

  function checkGoal(x, y) {
    return board[x][y] === BLOCK.goal;
  } // 현재 위치가 목표지점인지 검증하는 함수

  const startPos = getStartPos(board);
  board[startPos[0]][startPos[1]] = BLOCK.empty;
	// 시작지점을 찾고, bfs의 원할한 진행을 위해 시작지점을 빈공간으로 변경했다.

function bfs() {
    const arr = [[...startPos, NON_DIR, 0]];
    let idx = 0;
	// [시작x, 시작y, 방향, 이동횟수]를 담고, 배열idx를 0으로 설정
    
    while (1) {
      if (arr.length - 1 < idx) return;
	  // 더이상 검증할 수 있는 위치가 없다면 리턴

	  const [x, y, dir, cnt] = arr[idx++];
      const movedPath = `${x}/${y}/${dir}`;
      if (movedMap[movedPath]) continue;
      movedMap[movedPath] = true;
	  // 현재위치/이동방향을 기록하고 이미 반복한 정보라면 다음경우로 넘어간다.
        
      for (let i = 0; i < 4; i++) {
        let [nx, ny] = [x + dx[i], y + dy[i]];
		// i(방향)에 따라 다음 이동좌표가 이동가능한지 탐색해야한다.
        
        if (dir !== NON_DIR) {
          if (dir === i) continue;
          if (getReverseDir(dir) === i) continue;
          // 첫출발이 아니고, 이전의 이동방향이거나 이전 이동방향의 반대방향이면 pass.
        }
        if (endOfBoard(nx, ny)) continue;
        // 다음 이동방향이 board를 벗어났거나, 장애물이라면 갈 수 없다.

        while (!endOfBoard(nx + dx[i], ny + dy[i])) {
          [nx, ny] = [nx + dx[i], ny + dy[i]];
        } // 현재 가려는 방향(i)로 최대한 이동한다.
        // 다음 좌표가 board를 벗어났거나 장애물일 때 까지 이동할 것이다.

        if (checkGoal(nx, ny)) return cnt + 1;
        // 그렇게 멈춘 좌표가 목표지점이면 정답이다.
        arr.push([nx, ny, i, cnt + 1]);
        // 현재 좌표가 목표지점이 아니라면, 다음 탐색을 위해 arr에 넣어준다.
      }
    }
  }

  return bfs() ?? -1;
  // bfs가 숫자를 리턴했다면 정답이고, undefined를 리턴했다면 -1을 반환해주면 된다.
}