[백준] 13460번 구슬 탈출 2 - 자바스크립트

문제

13460번: 구슬 탈출 2

 

긴 문제와 조건을 기반으로 순서를 파악해 구현하는 구현유형이자 그래프 기반 BFS 유형이기도 하며 시뮬레이션 유형이기도 하다.

종합선물세트와도 같은 문제를 풀다가, 자그마한 실수를 개선하면서 정답이 나와서 정리하게 되었다.

자바스크립트로 코테 연습하는분들 화이팅

 

아무튼 여러분이 궁금한 것은 코드일테니, 가장 먼저 소개할 것은 성공을 출력해주는 코드이다.

풀이도 궁금하다면 이어서 계속 보면 되겠다.

---

코드

function sol(input) {
  let redBallPos = null;
  let blueBallPos = null;
  let holePos = null;
  const maxCnt = 10;
  const boardObj = {
    RED: 'R',
    BLUE: 'B',
    HOLE: 'O',
    EMPTY: '.',
  };
  const dirObj = {
    TOP: 0,
    RIGHT: 1,
    BOTTOM: 2,
    LEFT: 3,
  };

  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];

  const boards = input.slice(1).map((str, rowIdx) => {
    const row = str.split('');

    if (!redBallPos || !blueBallPos || !holePos) {
      row.forEach((elem, colIdx) => {
        if (elem === boardObj.RED) redBallPos = [rowIdx, colIdx];
        else if (elem === boardObj.BLUE) blueBallPos = [rowIdx, colIdx];
        else if (elem === boardObj.HOLE) holePos = [rowIdx, colIdx];
      });
    }

    return row;
  });

  boards[redBallPos[0]][redBallPos[1]] = boardObj.EMPTY;
  boards[blueBallPos[0]][blueBallPos[1]] = boardObj.EMPTY;

  function moveBall(ball, otherBall, dir) {
    while (1) {
      const nx = ball[0] + dx[dir];
      const ny = ball[1] + dy[dir];

      if (nx === otherBall[0] && ny === otherBall[1]) {
        break;
      } else if (boards[nx][ny] === boardObj.EMPTY) {
        ball[0] = nx;
        ball[1] = ny;
      } else if (boards[nx][ny] === boardObj.HOLE) {
        ball[0] = -1;
        ball[1] = -1;
        break;
      } else break;
    }
  }

  function checkEscape(ball) {
    if (ball[0] === -1 && ball[1] === -1) return true;
    return false;
  }

  function checkMoveRedballFirst(red, blue, dir) {
    if (
      (dir === dirObj.TOP && red[0] < blue[0]) ||
      (dir === dirObj.RIGHT && red[1] > blue[1]) ||
      (dir === dirObj.BOTTOM && red[0] > blue[0]) ||
      (dir === dirObj.LEFT && red[1] < blue[1])
    ) {
      return true;
    }
    return false;
  }

  function checkStop(bRed, aRed, bBlue, aBlue) {
    if (
      bRed[0] === aRed[0] &&
      bRed[1] === aRed[1] &&
      bBlue[0] === aBlue[0] &&
      bBlue[1] === aBlue[1]
    )
      return true;
    return false;
  }

  let answer = -1;
  let findAnswer = 0;
  const queue = [[...redBallPos, ...blueBallPos, 1]];

  while (queue.length) {
    if (findAnswer) break;
    const [rx, ry, bx, by, cnt] = queue.shift();

    for (let dir = 0; dir < 4; dir++) {
      const reds = [rx, ry];
      const blues = [bx, by];

      if (checkMoveRedballFirst(reds, blues, dir)) {
        moveBall(reds, blues, dir);
        moveBall(blues, reds, dir);
      } else {
        moveBall(blues, reds, dir);
        moveBall(reds, blues, dir);
      }

      if (checkEscape(blues)) continue;
      if (checkEscape(reds)) {
        findAnswer = 1;
        answer = cnt;
        break;
      }
      if (checkStop([rx, ry], reds, [bx, by], blues)) continue;
      if (cnt === maxCnt) continue;

      queue.push([...reds, ...blues, cnt + 1]);
    }
  }

  return answer;
}

const input = [];
require('readline')
  .createInterface(process.stdin, process.stdout)
  .on('line', (line) => {
    input.push(line);
  })
  .on('close', () => {
    console.log(sol(input));
    process.exit();
  });

 

풀이

문제가 꽤나 복잡해보이지만, 천천히 보면서 어떤 과정이 필요한지 분석해보자.
(문제가 구슬 탈출이지만, 공으로 착각해서 변수명이 ball이니 참고하길 바란다.)

 

문제의 조건
보드의 너비 M, 높이 N이 주어지며 3 <= N,M <= 10 이다.
보드 각 좌표에 문자열은 R(빨간공), B(파란공), O(구멍), #(벽), .(빈칸) 을 의미한다.

빨간공, 파란공을 상하좌우로 기울여서 빨간공만 구멍으로 빼낼 수 있는지 조사한다.
파란공이 탈출하거나 10회 이상으로 기울여야 한다면 -1을 반환한다.
10회 미만으로 기울여서 빨간공만 탈출시켰다면, 기울인 횟수를 출력한다.

 

문제 해결 과정

문제 해결을 위해 다음과 같은 과정을 거치도록 했다.

 

1. bfs로 탐색하며, [빨간공 위치, 파란공 위치, 반복수 cnt] 배열을 큐에 넣는다.
2. 큐가 비어있을 때 까지 탐색하면서 아래의 절차를 수행한다.

 

a. 상하좌우를 모두 탐색한다.
b. 탐색할 때 빨간공이 먼저 움직일지, 파란공이 먼저 움직일지를 이동할 방향과 각 공의 좌표에 따라 정한다.
c. 빨간공과 파란공을 정해진 순서대로 이동시킨다.
d. 파란공이 구멍에 빠졌다면 정답이 아니므로 넘어간다.
e. 빨간공만 구멍에 빠졌다면 정답이므로 탐색을 멈춘다.
f. 빨간공과 파란공이 빠지지 않았을 때 다음을 수행한다.
     i. 만약 cnt가 10회라면, 더이상 기울일 수 없으므로 다음 방향의 이동을 수행한다.
     ii. 빨간공과 파란공의 기울여서 움직인 좌표가 움직이기 전과 같다면, 큐에 넣지 않는다.
     iii. 움직인 좌표가 움직이기 전과 다르다면, 이후 좌표를 큐에 넣어주면서 기울인 횟수 cnt를 증가시킨다.

 

그리고 이 과정을 구현하기 위해 필요한 함수를 선언했다.

 

moveBall : 기울인 방향에 따라 공의 위치를 움직이는 함수이다.
checkEscape : 공이 구멍에 빠졌는지 검사한다.
checkMoveRedballFirst : 정해진 방향으로 이동하기 전에, 빨간공이 파란공보다 먼저 움직여야 하는지 검사한다.
checkStop : 공의 이동하기 전 위치와 이동한 후 위치가 동일한지 검사한다.

 

주의할 점은, 2차원 배열 boards을 이용해서 공을 직접 움직이면서 bfs 탐색을 수행하면 안된다는 것이다.

배열 내에서 직접 움직이며 탐색한다면, 상하좌우를 검색하면서 계속 boards에 있는 공을 움직이는 셈이다.

그러므로 필자는 배열에서 처음 공의 위치를 먼저 파악해서 기록한 다음, 공이 위치했던 boards 인덱스를 비웠다.

그리고 탐색하면서 각 케이스마다의 빨간공과 파란공의 위치를 기반으로 움직이도록 했다.

---

간단한 주석 첨부

function sol(input) {
  let redBallPos = null;
  let blueBallPos = null;
  let holePos = null;
  const maxCnt = 10;
  const boardObj = {
    RED: 'R',
    BLUE: 'B',
    HOLE: 'O',
    EMPTY: '.',
  }; // 상수 객체
  const dirObj = {
    TOP: 0,
    RIGHT: 1,
    BOTTOM: 2,
    LEFT: 3,
  }; // 상하좌우 방향 객체

  const dx = [-1, 0, 1, 0];
  const dy = [0, 1, 0, -1];

  const boards = input.slice(1).map((str, rowIdx) => {
    const row = str.split('');

    if (!redBallPos || !blueBallPos || !holePos) {
      row.forEach((elem, colIdx) => {
        if (elem === boardObj.RED) redBallPos = [rowIdx, colIdx];
        else if (elem === boardObj.BLUE) blueBallPos = [rowIdx, colIdx];
        else if (elem === boardObj.HOLE) holePos = [rowIdx, colIdx];
      });
    } // 빨간공, 파란공, 구멍의 위치 찾아서 기록하기

    return row;
  });

  boards[redBallPos[0]][redBallPos[1]] = boardObj.EMPTY;
  boards[blueBallPos[0]][blueBallPos[1]] = boardObj.EMPTY;
  // bfs 탐색을 수행해야 하므로, 보드에서 직접 이동시킨다면 매 수행마다 공의 위치가 바뀐다.
  // 그래서 보드에서 공 위치를 빈칸으로 남기고, 매 이동마다 상대적으로 위치를 파악한다.

  function moveBall(ball, otherBall, dir) {
    // 현재 이동시킬 공과 다른 공의 위치를 상대적으로 비교하며, 다른 공이 길을 막았을 때 넘어가지 않도록 한다.
    while (1) {
      const nx = ball[0] + dx[dir];
      const ny = ball[1] + dy[dir];

      if (nx === otherBall[0] && ny === otherBall[1]) {
        break;
      } else if (boards[nx][ny] === boardObj.EMPTY) {
        ball[0] = nx;
        ball[1] = ny;
      } else if (boards[nx][ny] === boardObj.HOLE) {
        // 먼저 이동한 공이 구멍에 빠졌다면, 뒤에 이동할 공도 구멍에 빠질 수 있으므로, (-1,-1)좌표를 부여한다.
        ball[0] = -1;
        ball[1] = -1;
        break;
      } else break;
    }
  }

  function checkEscape(ball) {
    // 공이 구멍에 빠졌다면 (-1, -1) 좌표를 가지므로 이를 확인한다.
    if (ball[0] === -1 && ball[1] === -1) return true;
    return false;
  }

  function checkMoveRedballFirst(red, blue, dir) {
    // 이동방향에 따라 이동방향과 더 가까운 공을 먼저 이동시킨다.(Ex.방향이 좌측이면 더 왼쪽에 위치한 공)
    if (
      (dir === dirObj.TOP && red[0] < blue[0]) ||
      (dir === dirObj.RIGHT && red[1] > blue[1]) ||
      (dir === dirObj.BOTTOM && red[0] > blue[0]) ||
      (dir === dirObj.LEFT && red[1] < blue[1])
    ) {
      return true;
    }
    return false;
  }

  function checkStop(beforeBall, afterBall) {
      // 공의 이동 전과 이동 후의 위치가 동일한지 검사한다. 빨간공, 파란공 둘다 동일하다면 더이상 큐로 탐색할 필요가 없다.
    if (beforeBall[0] === afterBall[0] && beforeBall[1] === afterBall[1])
      return true;
    return false;
  }

  let answer = -1;
  let findAnswer = 0;
  const queue = [[...redBallPos, ...blueBallPos, 1]];
  // 두 공의 처음 위치를 큐에 넣어주고 시작한다.

  while (queue.length) {
    if (findAnswer) break;
    const [rx, ry, bx, by, cnt] = queue.shift();

    for (let dir = 0; dir < 4; dir++) {
      const reds = [rx, ry];
      const blues = [bx, by];

      if (checkMoveRedballFirst(reds, blues, dir)) {
        // 빨간공을 먼저 이동시키고, 파란공을 나중에 이동시킨다.
        // reds, blues 배열의 0,1번 인덱스 값은 moveBall 함수 수행에 따라 변화하게 된다.
        moveBall(reds, blues, dir);
        moveBall(blues, reds, dir);
      } else {
        moveBall(blues, reds, dir);
        moveBall(reds, blues, dir);
      }

      // 파란공이 빠졌다면, 무조건 정답이 아니다.
      if (checkEscape(blues)) continue;
      if (checkEscape(reds)) {
        // 빨간공만 빠졌다면 정답이다.
        findAnswer = 1;
        answer = cnt;
        break;
      }
      // 빨간공과 파란공 둘 다 제자리라면, 이동한 좌표를 큐에 넣을 필요가 없다.
      if (checkStop([rx, ry], reds) && checkStop([bx, by], blues)) continue;
      // 10회의 이동까지 정답을 못찾았다면, 더이상 탐색하지 않는다.
      if (cnt === maxCnt) continue;

      // 더 탐색할 수 있다면 큐에 넣어준다.
      queue.push([...reds, ...blues, cnt + 1]);
    }
  }

  return answer;
}

// 입력 처리
const input = [];
require('readline')
  .createInterface(process.stdin, process.stdout)
  .on('line', (line) => {
    input.push(line);
  })
  .on('close', () => {
    console.log(sol(input));
    process.exit();
  });