[Javascript] 백준 - Puyo Puyo

목차

1. 문제 설명
2. 문제 풀이
3. 정답 코드

---

1. 문제 설명

'뿌요뿌요'는 같은 색상끼리 터트리는  게임이다. 
 

🌱 뿌요뿌요 규칙
1) 같은 색상이 4개 이상이 있을 때 (인접한 상하좌우 4개 이상), 터뜨린다.
2) 만약 터뜨릴 수 있는 것들이 여러 집단일 때, 동시에 터뜨린다.

 
이과정을 몇번 반복하는 지 카운트하는 문제이다.

---

2. 문제 풀이

1) DFS를 순회하며, 4개 이상인지 확인하기

 - dfs 함수를 사용하여 같은 색깔의 블록을 탐색한다. 탐색한 블록의 좌표를 record 배열에 저장한다.

 
2) 4개 이상일 경우, 다녀간 경로를 모두 터뜨리기

 - 탐색이 끝난 후, record 배열의 길이가 4이상이면 해당 블록들을 터뜨린다.
 - 터뜨린다는 것을 '.' 로 만드는 것이다.

 

3) 모두 터뜨린 다음 그리드를 재정리하기

 - 터뜨린 후, 그리드를 아래에서 위로 재정리하며 빈 공간을 채운다.

 
사실 이 부분은 스스로 구현을 못했고, 생각도 안났던....
그래서 이해하기 쉽게 그림으로 표현해보았다.

---

2. 정답 코드

const fs = require("fs");
const input = fs.readFileSync("./example.txt", "utf8").trim().split("\n");

var grid = input.slice().map((line) => line.split(""));

// 뿌요 그리드의 행, 열
var ROW = 12;
var COL = 6;

var dr = [0, 1, 0, -1];
var dc = [1, 0, -1, 0];

var answer = 0;
var visited = [];
var record = [];

function dfs(r, c) {
  visited[r][c] = 1;
  record.push([r, c]);

  for (let i = 0; i < 4; i++) {
    var nr = r + dr[i];
    var nc = c + dc[i];

    if (
      0 <= nr &&
      nr < ROW &&
      0 <= nc &&
      nc < COL &&
      grid[nr][nc] === grid[r][c] &&
      !visited[nr][nc]
    ) {
      dfs(nr, nc);
    }
  }
}

while (true) {
  var flag = 0;
  visited = Array.from({ length: ROW }, () =>
    Array.from({ length: COL }).fill(0)
  );

  for (let i = 0; i < ROW; i++) {
    for (let j = 0; j < COL; j++) {
      if (grid[i][j] !== "." && !visited[i][j]) {
        record = [];
        dfs(i, j);

        if (record.length >= 4) {
          for (const [r, c] of record) {
            grid[r][c] = ".";
          }
          flag = 1;
        }
      }
    }
  }

  if (!flag) break;

  for (let j = 0; j < COL; j++) {
    let q = [];
    for (let i = 11; i >= 0; i--) {
      if (grid[i][j] !== ".") {
        q.push(grid[i][j]);
      }
    }

    for (let i = 0; i < q.length; i++) {
      grid[11 - i][j] = q[i];
    }
    for (let i = q.length; i < ROW; i++) {
      grid[11 - i][j] = ".";
    }
  }

  answer++;
}

console.log(answer);

 
배운점
나는 구현에서 약하다는 것을 다시 한번 느꼈다. 시간 복잡도 신경쓰지 않고, 완전탐색으로 구현을 먼저 생각하는 습관을 들여야겠다!