[JS] 백준 17780 새로운 게임

백준 17780 새로운 게임

풀이

각 칸에 저장해야 할 정보는 가장 아래 있는 말, 가장 위에 있는 말, 칸에 있는 말의 수입니다. 쌓인 말의 이동은 가장 밑에 있는 말에 의해 정해지고 빨강 칸으로 이동할 때, 쌓인 말의 순서를 반대로 뒤집지만 가장 위에 있는 말의 정보만 알아도 상관없기 때문입니다.

저장해야 할 말의 정보는 번호와 방향 뿐입니다. 라운드마다 말이 순서대로, 정해진 방향으로 이동해야 하기 때문입니다.

이러한 정보들을 가지고 각 칸의 색에 따라 조건을 잘 생각하면서 구현하면 되는 간단한 문제입니다.

코드

const fs = require('fs')
const filePath = process.platform === 'linux' ? 'dev/stdin' : './input.txt'
const input = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split('\n')
  .map((el) => el.split(' ').map(Number))

class Piece {
  constructor() {
    this.bottom = { number: 0, dir: -1 }
    this.top = { number: 0, dir: -1 }
    this.count = 0
  }
}

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

const [N, K] = input.shift()

const board = Array.from(Array(N), () => Array(N))
for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) board[i][j] = new Piece()
}
const sequence = Array(K + 1)
const empty = { number: 0, dir: -1 }

for (let i = 0; i < K; i++) {
  const temp = input.pop()

  board[temp[0] - 1][temp[1] - 1].bottom.number = K - i
  board[temp[0] - 1][temp[1] - 1].bottom.dir = temp[2] - 1
  board[temp[0] - 1][temp[1] - 1].count = 1

  sequence[K - i] = { x: temp[0] - 1, y: temp[1] - 1 }
}

let round = 0

while (++round <= 1000) {
  let flag = false

  for (let i = 1; i <= K; i++) {
    if (board[sequence[i].x][sequence[i].y].bottom.number !== i) continue

    let dir = board[sequence[i].x][sequence[i].y].bottom.dir
    let nx = sequence[i].x + dx[dir]
    let ny = sequence[i].y + dy[dir]

    if (nx < 0 || ny < 0 || nx >= N || ny >= N || input[nx][ny] === 2) {
      //파랑
      switch (dir) {
        case 0:
          dir = 1
          break
        case 1:
          dir = 0
          break
        case 2:
          dir = 3
          break
        case 3:
          dir = 2
          break
      }

      board[sequence[i].x][sequence[i].y].bottom.dir = dir
      nx = sequence[i].x + dx[dir]
      ny = sequence[i].y + dy[dir]

      if (nx < 0 || ny < 0 || nx >= N || ny >= N || input[nx][ny] === 2) {
        // 방향만 변경
        continue
      } else if (input[nx][ny] === 1) {
        // 빨강
        red(sequence[i].x, sequence[i].y, nx, ny)
      } else {
        // 흰 칸
        white(sequence[i].x, sequence[i].y, nx, ny)
      }
    } else if (input[nx][ny] === 0) {
      // 흰 칸
      white(sequence[i].x, sequence[i].y, nx, ny)
    } else if (input[nx][ny] === 1) {
      // 빨강
      red(sequence[i].x, sequence[i].y, nx, ny)
    }

    sequence[board[nx][ny].bottom.number].x = nx
    sequence[board[nx][ny].bottom.number].y = ny

    if (board[nx][ny].count >= 4) {
      flag = true
      break
    }
  }
  if (flag) break
}

if (round > 1000) console.log(-1)
else console.log(round)

function red(x, y, nx, ny) {
  if (board[nx][ny].bottom.number === 0) {
    if (board[x][y].top.number === 0) {
      board[nx][ny].bottom = { ...board[x][y].bottom }
      board[x][y].bottom = { ...empty }
    } else {
      board[nx][ny].bottom = { ...board[x][y].top }
      board[nx][ny].top = { ...board[x][y].bottom }
      board[x][y].bottom = { ...empty }
      board[x][y].top = { ...empty }
    }
  } else {
    board[nx][ny].top = { ...board[x][y].bottom }
    board[x][y].bottom = { ...empty }
    board[x][y].top = { ...empty }
  }
  board[nx][ny].count += board[x][y].count
  board[x][y].count = 0
}

function white(x, y, nx, ny) {
  if (board[nx][ny].bottom.number === 0) {
    board[nx][ny].bottom = { ...board[x][y].bottom }
    board[nx][ny].top = { ...board[x][y].top }
    board[x][y].bottom = { ...empty }
    board[x][y].top = { ...empty }
  } else if (board[x][y].top.number === 0) {
    board[nx][ny].top = { ...board[x][y].bottom }
    board[x][y].bottom = { ...empty }
  } else {
    board[nx][ny].top = { ...board[x][y].top }
    board[x][y].bottom = { ...empty }
    board[x][y].top = { ...empty }
  }
  board[nx][ny].count += board[x][y].count
  board[x][y].count = 0
}

알게 된 것

2차원 배열을 선언할 때 보통 false나 0으로 채워진 배열을 다음과 같이 선언하여 자주 사용했습니다.

const arr = Array.from(Array(N), () => Array(N).fill(false))

그래서 Piece객체를 지니는 배열을 선언할 때도 단순하게

const arr = Array.from(Array(N), () => Array(N).fill(new Piece()))

이렇게 했는데 모든 배열의 칸이 하나의 객체를 공유하는 문제가 발생하였습니다.
이는 fill()이 value로 reference type이 전달되면 참조값을 저장하는 함수이기 때문이었습니다.
따라서 이럴 경우 for문을 통해 초기값을 채워줘야 합니다.