백준 17837번 새로운 게임 2 풀이

• solved.ac 의 그래프를 간만에 보니 시뮬레이션이나 구현 쪽 문제를 많이 안 풀어본 것 같길래? 간만에 알고리즘 문제 풀이를 재개했다.

---

문제 풀이 - 백준 17837번 새로운 게임 2

  구현/시뮬레이션 문제로, 주어진 룰에 맞춰 게임을 진행한 후, 게임 종료 조건을 만족하는 턴이 언제인지를 구하는 문제이다. 조건은 아래와 같다.

• N x N 체스판이 주어진다. 이 체스판은 각 칸이 흰색(0), 빨간색(1), 파란색(2)중 한 색으로 칠해져있다.
• 1번부터 K번 까지의 말이 존재하고, 이 말은 각각 진행할 수 있는 방향이 정해져있다.
• 체스판 한 칸 위에 복수의 말이 존재할 수 있다. 이 때, 말을 아래에서 위로 차례로 쌓는다.
• 1번부터 K번 까지의 말은 순서대로 자신의 정해진 방향에 따라 한 칸씩 이동하는데, 이 때 목적지 칸의 색깔에 따라 이동방식이 바뀐다.
  • 흰색이면 이동하려는 칸에 이미 존재하는 말들 위에 자신들이 올라간다.
  • 빨간색이면 이동하려는 칸에 이미 존재하는 말들 위에 자신들이 올라가되, 순서를 반대로 바꾼다.
    
  • 파란색이면 자신의 이동방향을 반대로 바꾸고 한 칸 이동한다.
    • 이 때, 방향을 바꾼 후 이동하려는 칸이 파란색이면 이동하지 않는다.
  • 체스판을 벗어나는 경우 파란색과 같이 행동한다.
• 한 칸에 쌓인 말들이 4개 이상인 칸이 생기면 게임을 종료한다.

 

  이래저래 조건이 꽤 붙어있는데, 구현 방법을 떠올리는데 큰 어려움이 들지는 않았다. 아래와 같은 방법을 구상했다.

• 현재 말들이 어디에, 어떻게 쌓여있는지 알아야하므로 3차원 배열을 만들어 이 정보를 관리한다.
• 이동하려는 칸에 이미 존재하는 말들 위에 새로운 말들을 쌓을 때는 splice 와 reverse 메서드를 사용하면 된다.
  • splice를 통해 기존 칸에서 옮길 말들을 떼어올 수 있으며, reverse 메서드로 이동하려는 칸이 빨간 칸일 때의 조건을 충족할 수 있다.
• 게임 종료 조건을 탐색하기 위해, 이동이 끝난 후 해당 칸에 쌓인 말들의 개수를 체크한다.

 

  ...이리하여 구현 코드를 작성했는데, 문제의 예시 입력 5에서 자꾸만 오답이 나오는 것이었다. 어찌된 일인가 했는데, 다행히 게시판에서 원인을 빠르게 찾을 수 있었다.

  문제에서 별달리 언급이 되지 않아서 간과하고 넘어갔는데, 이동하려는 칸이 파란색인 경우(혹은 체스판을 벗어나는 경우) 방향을 바꾸고 진행한 칸이 빨간색이면 또다시 빨간색 칸의 룰을 따라야 한다! 전혀 생각도 못한 곳에서 걸려서 한참을 오류 잡기에 힘썼다.

  또한 깜빡했던 부분으로, 이동을 완료한 말들의 위치를 갱신해주는 것이 있다. 나는 앞서 언급했듯 말들의 위치를 별도로 관리하므로, 이 위치 배열을 한 번 업데이트 해주는 과정이 필요하다.

 

  모든 에러를 잡고 통과한 코드가 아래의 코드이다.

 

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

let input = [];

// 다음 위치를 구하기 위해 값을 미리 정해둔다
const nextX = [0, 0, 0, -1, 1];
const nextY = [0, 1, -1, 0, 0];

rl.on("line", (line) => {
  input.push(line.split(" ").map((el) => parseInt(el)));
}).on("close", function () {
  const [n, k] = input.shift();
  const board = input.splice(0, n);
  let answer = 0;
  let isOver = false;

  // 현재 말들이 어떻게 쌓여있는지를 나타내는 3차원 배열
  const currentBoard = Array.from(Array(n), () =>
    Array.from(Array(n), () => [])
  );

  // 1번부터 K번까지의 말들의 위치 및 방향을 나타내는 배열
  const location = input.map((el) => {
    const [x, y, direction] = el;
    return [x - 1, y - 1, direction];
  });

  // 현재 보드를 초기 위치로 초기화
  for (let num = 0; num < k; num++) {
    const [currentX, currentY] = location[num];

    currentBoard[currentX][currentY].push(num);
  }

  const isInRange = (x, y) => {
    return 0 <= x && 0 <= y && x < n && y < n;
  };

  while (answer <= 1000 && !isOver) {
    for (let i = 0; i < k; i++) {
      const [curX, curY, direction] = location[i];

      const nX = curX + nextX[direction];
      const nY = curY + nextY[direction];

      // 다음 칸이 파란색이거나 체스판을 벗어나는 경우
      if (!isInRange(nX, nY) || board[nX][nY] === 2) {
        // 방향을 재설정한다
        const newDirection =
          direction % 2 === 1 ? direction + 1 : direction - 1;
        const nX2 = curX + nextX[newDirection];
        const nY2 = curY + nextY[newDirection];

        location[i][2] = newDirection;

        // 재설정한 방향으로 나아갈 때, 다음 칸이 흰색이거나 빨간색일 경우
        if (isInRange(nX2, nY2) && board[nX2][nY2] !== 2) {
          const curIdx = currentBoard[curX][curY].findIndex((el) => el === i);
          const arrToMove = currentBoard[curX][curY].splice(curIdx);

          if (board[nX2][nY2] === 0) {
            // 흰색
            currentBoard[nX2][nY2].push(...arrToMove);
          } else {
            // 빨간색, 말들을 거꾸로 쌓아준다
            arrToMove.reverse();
            currentBoard[nX2][nY2].push(...arrToMove);
          }

          // 이동하는 말들의 위치를 새로운 값으로 갱신한다
          for (let idx = 0; idx < arrToMove.length; idx++) {
            location[arrToMove[idx]][0] = nX2;
            location[arrToMove[idx]][1] = nY2;
          }
          
          // 이동이 끝나고 게임이 끝났는지 아닌지 확인한다
          if (currentBoard[nX2][nY2].length >= 4) isOver = true;
        }
      } else if (board[nX][nY] === 0) {
        const curIdx = currentBoard[curX][curY].findIndex((el) => el === i);
        const arrToMove = currentBoard[curX][curY].splice(curIdx);
        currentBoard[nX][nY].push(...arrToMove);

        for (let idx = 0; idx < arrToMove.length; idx++) {
          location[arrToMove[idx]][0] = nX;
          location[arrToMove[idx]][1] = nY;
        }

        if (currentBoard[nX][nY].length >= 4) isOver = true;
      } else if (board[nX][nY] === 1) {
        const curIdx = currentBoard[curX][curY].findIndex((el) => el === i);
        const arrToMove = currentBoard[curX][curY].splice(curIdx);
        arrToMove.reverse();
        currentBoard[nX][nY].push(...arrToMove);

        for (let idx = 0; idx < arrToMove.length; idx++) {
          location[arrToMove[idx]][0] = nX;
          location[arrToMove[idx]][1] = nY;
        }

        if (currentBoard[nX][nY].length >= 4) isOver = true;
      }
    }

    answer++;
  }

  if (answer > 1000) {
    console.log(-1);
  } else console.log(answer);

  process.exit();
});

 

  어찌저찌 정답은 나왔지만 오래 고민하기도 했고 코드가 꽤 늘어지는 것 같아 아쉽기도 하다.

 

---

• 근래 깨달았는데 너무 백준만 풀고 프로그래머스 쪽 문제를 많이 안 건드려본 것 같아서, 앞으로는 프로그래머스 문제도 많이 다뤄볼 예정이다.
• 구현이나 시뮬레이션 문제는 뭔가... 이론이 복잡하다기 보다는 코드 작성 자체에서 시간을 소모할 때가 많은 것 같다. 풀이 방법은 머릿속에서 어떻게 정리가 되었는데 그게 내 코드로 표현이 안 되는 느낌....