문제
뿌요뿌요의 룰은 다음과 같다.
필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다.
뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된다.
뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.
아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지게 되는데, 터진 후 뿌요들이 내려오고 다시 터짐을 반복할 때마다 1연쇄씩 늘어난다.
터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.
남규는 최근 뿌요뿌요 게임에 푹 빠졌다. 이 게임은 1:1로 붙는 대전게임이라 잘 쌓는 것도 중요하지만, 상대방이 터뜨린다면 연쇄가 몇 번이 될지 바로 파악할 수 있는 능력도 필요하다. 하지만 아직 실력이 부족하여 남규는 자기 필드에만 신경 쓰기 바쁘다. 상대방의 필드가 주어졌을 때, 연쇄가 몇 번 연속으로 일어날지 계산하여 남규를 도와주자!
입력
총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다.
이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다.
R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다.
입력으로 주어지는 필드는 뿌요들이 전부 아래로 떨어진 뒤의 상태이다. 즉, 뿌요 아래에 빈 칸이 있는 경우는 없다.
출력
현재 주어진 상황에서 몇연쇄가 되는지 출력한다. 하나도 터지지 않는다면 0을 출력한다.
예제 입력
......
......
......
......
......
......
......
......
.Y....
.YG...
RRYG..
RRYGG.
예제 출력
3
내가 했던 풀이 방법
뿌요뿌요의 진행 순서를 정리하면 다음과 같다.
1. 4개 이상의 같은 색깔 그룹이 있는지를 찾는다.
2. 모든 위치에서 그룹을 찾았다면, 찾은 그룹들을 전부 제거한다. (터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터져야 하고 여러 그룹이 터지더라도 한번의 연쇄가 추가된다.는 조건이 있기 때문에 찾고 제거한 뒤 다음 그룹을 찾는 게 아니라 모두 찾은 뒤에 삭제하는 방식으로 구현했다.)
3. 뿌요가 제거되었다면 중력에 의해 위에 있는 뿌요가 내려온다.
4. 1~3번을 다해주면 1 연쇄가 끝나고, 재배치된 뿌요 중에 터질 그룹이 있는지를 찾는 걸 반복한다.
- playPuyo 함수를 실행한다. 이 함수는 재귀적으로 반복한다. 재귀가 끝나는 조건은 deleteIdx의 길이가 0일 때이다. 즉, 터질 뿌요가 없을 때까지 반복한다.
- playPuyo에서는 visited를 초기화해준다. 여기서 visited는 BFS에서 활용되며, 해당 뿌요가 체크가 되었는지를 확인해 연산을 효율적으로 하게끔한다. deleteIdx는 이번 연쇄에서 사라질 뿌요의 위치가 담겨있다.
- 모든 위치를 탐색했을 때 해당 위치에 뿌요가 존재하고 체크되지 않았을 때 그 위치를 기준으로 BFS를 진행한다.
- BFS는 일반적인 BFS와 동일한 방식으로 진행된다. 상하좌우를 기준으로 같은 색깔을 가진 뿌요들의 위치를 group에 담는다. BFS가 끝나면, group을 반환한다. 즉, 반환값은 해당 위치에서 찾았을 때 같은 색깔의 뿌요들의 위치 배열이다.
- BFS의 반환값의 length가 4 이상이면 제거될 뿌요이므로 해당 위치를 deleteIdx에 넣어준다. 모든 위치에 대해 3~5번을 진행한 뒤에는 deleteIdx에는 한 번의 연쇄에서 삭제될 모든 뿌요의 위치가 담겨있다.
- deleteIdx가 존재한다면, 이를 y방향을 기준으로 정렬해준 뒤, deletePuyo를 실행한다. deletePuyo는 뿌요들을 삭제하면서 뿌요의 위치를 재배치해준다.
- deleteIdx를 받은 deletePuyo는 해당 위치를 "."으로 바꿔준다. 그리고 해당 y방향을 시작하여 0으로(위로) y 방향을 감소하면서 해당 위치에 바로 위가 0 이상이면서 "."이 아닐 경우 둘의 위치를 바꿔준다. 쉽게 말하면 x 방향 신경쓰지 않고 3층의 뿌요가 제거되어 "."가 되었을 때 2층의 뿌요가 존재한다면 3층과 2층을 swap 해주는 것이다. (여기서 층은 0층이 가장 윗층임에 유의) 만약 바로 위가 board 영역을 벗어나거나 "."이라면 위는 더 이상 뿌요가 존재하지 않는다. (위에서부터 순차적으로 뿌요를 재배치해왔고 제거와 동시에 내려주고 있기 때문에) 이 경우 바로 break하여 불필요한 연산을 줄인다.
- 모든 뿌요가 재배치되면 다시 연쇄 수를 1 증가하고 playPuyo를 실행하여 다음 연쇄를 진행한다. 모든 재귀가 끝난 뒤에 answer에는 연쇄 수가 담겨있게 된다.
코드
const fs = require('fs');
let [...board] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');
board = board.map((i) => i.trim().split(''));
let visited = Array.from({ length: 12 }, () => Array(6).fill(false));
let answer = 0;
let move = [
[0, 1],
[0, -1],
[-1, 0],
[1, 0],
];
function BFS(start) {
let queue = [start];
visited[start[0]][start[1]] = true;
let group = [];
while (queue.length) {
let [idY, idX] = queue.shift();
group.push([idY, idX]);
for (let i = 0; i < 4; i++) {
let newY = idY + move[i][0];
let newX = idX + move[i][1];
if (
newY >= 0 &&
newY < 12 &&
newX >= 0 &&
newX < 6 &&
!visited[newY][newX] &&
board[start[0]][start[1]] === board[newY][newX]
) {
queue.push([newY, newX]);
visited[newY][newX] = true;
}
}
}
return group;
}
function deletePuyo(arr) {
for (let i = 0; i < arr.length; i++) {
let [y, x] = arr[i];
board[y][x] = '.';
for (let j = y; j > 0; j--) {
if (j - 1 >= 0 && board[j - 1][x] !== '.') {
[board[j][x], board[j - 1][x]] = [board[j - 1][x], board[j][x]];
} else break;
}
}
}
function playPuyo() {
visited = Array.from({ length: 12 }, () => Array(6).fill(false));
let deleteIdx = [];
for (let i = 0; i < 12; i++) {
for (let j = 0; j < 6; j++) {
if (!visited[i][j] && board[i][j] !== '.') {
let group = BFS([i, j]);
if (group.length >= 4) {
deleteIdx.push(...group);
}
}
}
}
if (deleteIdx.length > 0) {
deleteIdx.sort((a, b) => a[0] - b[0]);
deletePuyo(deleteIdx);
playPuyo();
answer++;
}
}
playPuyo();
console.log(answer);회고
수학적인 개념 없는 빡구현은 너무 재밌는 것 같다... 생각보다 잘 풀렸는데 혹시 몰라서 반례들을 체크해보니 오류가 나는 구간이 있어서 잘못 구현했나... 싶었는데 과정마다 board를 출력해보니 제거될 뿌요가 y방향으로 정렬되지 않으면 deletePuyo가 제대로 동작하지 않는다는 걸 알게 됐다 반례 먼저 체크하길 잘했지만... 미리 그걸 생각했다면 더 좋았을텐데..!!
