[백준11559_자바스크립트(javascript)] - Puyo Puyo

🔴 문제

Puyo Puyo

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\r\n')
  .map((it) => it.split(''));
const puyo = Array.from({ length: 6 }).map((_) => []);

const printMap = (map) => {
  for (let i = 0; i < map.length; i++) console.log(map[i].join(' '));
};

// 뿌요를 옆으로 눕힘
for (let i = 11; i >= 0; i--) {
  for (let j = 0; j < 6; j++) {
    puyo[j].push(inputs[i][j]);
  }
}

let visited = puyo.map((it) => [...it]);

// 뿌요를 업데이트해줌
const makeNewPuyo = (puyo) => {
  for (let i = 0; i < 6; i++) {
    const newPuyo = puyo[i].filter((it) => it !== '.');

    while (newPuyo.length !== 12) {
      newPuyo.push('.');
    }

    puyo[i] = newPuyo;
  }
};

// 뿌요를 부심
const crushPuyo = (puyo, visited) => {
  for (let i = 0; i < 6; i++) {
    for (let j = 0; j < 12; j++) {
      if (visited[i][j] === true) puyo[i][j] = '.';
    }
  }
};

// 뿌요가 연결되어 있는지 확인
const dfs = (x, y, target) => {
  if (x < 0 || y < 0 || x >= 6 || y >= 12) return false;

  if (visited[x][y] === target) {
    visited[x][y] = true;
    size += 1;

    dfs(x + 1, y, target);
    dfs(x - 1, y, target);
    dfs(x, y + 1, target);
    dfs(x, y - 1, target);

    return true;
  }

  return false;
};

// 코드의 시작 맵을 돌면서 상태 확인
let size = 0;
let breakLevel = 0;
let isBreak = false;
while (true) {
  makeNewPuyo(puyo);

  for (let i = 0; i < 6; i++) {
    for (let j = 0; j < 12; j++) {
      visited = puyo.map((it) => [...it]);

      if (puyo[i][j] !== '.' && dfs(i, j, puyo[i][j])) {
        if (size >= 4) {
          crushPuyo(puyo, visited);
          isBreak = true;
        }

        size = 0;
      }
    }
  }

  if (!isBreak) break;
  breakLevel += 1;
  isBreak = false;
}

// 결과를 출력
console.log(breakLevel);

🟢 풀이

⏰ 소요한 시간 : 2시간

골드 4의 구현 문제!
뿌요뿌요에 중력을 작용시키려면 배열의 요소를 회전시켜줘야 하는데 이를 구현하기 위해서는 뿌요를 옆으로 눕혀야 한다고 생각했다.
그래서 먼저 뿌요맵을 옆으로 눕혀 다음과 같은 형태를 만들어준다. 그래야 같은 줄에 중력을 작용하기 쉽다.

. . . . . . . . . . . .
Y Y Y B G G B B B Y . .
B G G G B B G G G G . .
B G G G B Y Y Y Y B . .
B Y Y G Y . . . . . . .
. . . . . . . . . . . .

그 후, while문에서 뿌요로직을 수행해준다. 뿌요 로직을 수행하기 전에는 뿌요 맵에 중력이 작용된 상태여야 하므로 중력을 적용하여 새로운 뿌요맵을 만들어주는 makeNewPuyo함수를 수행해준다.
makeNewPuyo 함수는 총 6개의 줄을 확인할텐데, .를 필터링하여 문자만 남긴 newPuyo 배열을 만들고, 길이가 12가 될때까지 .를 푸시해준다. 그리고 기존 뿌요맵을 교체해주면 된다.
그리고 이제 뿌요가 네 개 이상 연결되어 있는지 확인해야 한다. 그래서 dfs를 수행해줘야 하는데 dfs를 수행할 visited를 만들어준다. 그리고 뿌요맵을 순회하면서 요소가 문자일때만 dfs를 수행해준다. 전역변수 size를 만들어 dfs를 한 번 수행할 때마다 size의 값을 1 증가시켜주고, size의 값이 4 이상일 경우, 뿌요를 터뜨려주는 crushPuyo 함수를 수행한다.
crushPuyo 함수 내부에서는 뿌요맵과 방문배열을 비교하며 방문했던 애들만 .으로 바꿔주면 된다. 한 번이라도 뿌요가 터졌다면 isBreak를 true로 바꿔 연쇄작용이 발생했음을 기억한다.
만약 연쇄작용이 발생하지 않았다면 정답을 출력하고, 아니라면 while문을 다시 수행한다.

🔵 Ref