[JS] 백준 11559 : PuyoPuyo - 구현문제

https://www.acmicpc.net/problem/11559

11559번: Puyo Puyo

 

 

📋풀이방법

1. 아래에서부터 컬러블럭이있는 곳을 찾는다

2. 컬러블럭을 찾으면 DFS를 실행한다.

3. 상하좌우로 같은 색상의 블럭이 있으면 P_cnt를 카운트해준다.

4. 그 주변의 컬러블럭을 모두 카운트해주면서 P_arr에 좌표를 넣어준다.

5. DFS가 끝나고 만약 P_cnt가 4이상이라면 P_arr에 넣어줬던 좌표를 일단 P_arr_clear에 저장한다

 -연쇄는 한번에 일어나므로

 

6. 모든 게임 보드판을 돌면서 DFS를 실행하여 P_arr_clear에 연쇄되는 좌표를 넣었다면 터진 부분을 모두 "."으로 바꿔준다.

7. 이제 모든 게임보드판을 아래에서 위로 행을 기준으로 순회하면서 블럭을 위에서 아래로 내려야한다.

8.만약 아래에서 순회하면서 "."블럭이 있다면

9.그 순간 그 열을 기준으로 위에 컬러블럭이있는지 검사한다.

10. 컬러블럭이 있다면 컬러블럭과 위에서 찾은"."블럭의 좌표를 서로 바꿔준다.

11. 그리고 검사하는 좌표였던 부분을 위로 올려준다 ( j-- )

12. 모두 아래로 내렸다면 이전에 연쇄가 일어났었는지 확인하고 일어났다면 answer을 +1 증가시켜준다.

13.만약 연쇄가 안일어났다면 게임을 종료시킨다.

 

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

let arr=[];
for(var i=0;i<12;i++){
    arr.push(input.shift().split(""));
}

let dx=[1,0,0,-1];
let dy=[0,1,-1,0];

let visited=[];

let result=0;

//같은색 4개 찾기
let P_cnt=0;
let P_arr=[];
let P_arr_clear=[];

function DFS(y,x,color){
    for(var i=0;i<4;i++){
        let nx=x+dx[i];
        let ny=y+dy[i];
        if(nx>=0 && ny>=0 && nx<6 && ny<12 && visited[ny][nx]==0){
            if(arr[ny][nx]==color){
                visited[ny][nx]=1;
                P_cnt++;
                P_arr.push([ny,nx])
                DFS(ny,nx,color);
            }
        }
    }
    
}
let flag=false;

while(1){
    flag=false;
    visited=Array.from({length:12},()=>Array(6).fill(0));
    P_arr_clear=[];
    for(var i=11;i>=0;i--){
        for(var j=0;j<6;j++){
            if(arr[i][j]!="." && visited[i][j]==0){
                visited[i][j]=1;
                P_cnt=1;
                P_arr.push([i,j]);
                DFS(i,j,arr[i][j]);
                if (P_cnt>= 4)
                    {
                        flag=true;  // 뿌요가 터졌다고 표시.
                        for (var k = 0; k<P_arr.length; k++)    
                        {
                            P_arr_clear.push(P_arr[k]);    // 해당 좌표들 옮겨주기
                        }
                    }
                    P_arr=[];
            }

        }

    }
    //터진부분 "."로 바꿔주기
    for(var i=0;i<P_arr_clear.length;i++){
        let [y,x]=P_arr_clear[i];
        arr[y][x]=".";
    }
    
    //위에서 아래로 내리기
    for(var i=0;i<6;i++){
        for(var j=11;j>=0;j--){
            if(arr[j][i]=="."){
                for(var k=j-1;k>=0;k--){
                    if(arr[k][i]!="."){
                        console.log(arr)
                        arr[j][i]=arr[k][i];
                        arr[k][i]="."
                        j--;
                    }
                }
                
            }
        }
    }
    
    if(flag) result++;
    else break;
}



console.log(result)

 

💢어려웠던점

1. 계속해서 좌표를 실수했다. 

 -예를 들어 y좌표와 x좌표를 거꾸로 쓴다던지 변수를 자꾸 잘못입력해서 꼬인다던지 실수했음

2. DFS로 컬러블럭을 찾을 때 P_cnt라는 변수를 이용해서 4개 이상이되면 DFS가 끝나는게 아닌 모든 인접해있는 컬러블럭을 찾은 후에 제거를 해야되는 것이였다.

-처음에는 DFS(L, ... ) 을 줘서 if(L>=4) 이런 식으로 하려고 했는데 문제의 조건인 4개이상의 블럭과 맞지 않았다.

-P_cnt라는 변수로 일단 DFS를 돌면서 카운트만해주고 DFS가 모두 끝난후에 if조건으로 4이상임을 확인하면 됐었다.

3. 블럭을 위에서 아래로 내릴 때 for문 변수를 -- 해줘야하는데 집중을 못해서 다른 부분에서 ++을 해주거나 +1을 해줬다.

-동그라미 친 부분이 잘못된 부분이다. 저런 사소한 실수로 계속 시간을 소비했다.

 

https://www.acmicpc.net/board/view/119626

글 읽기 - 테스트케이스 12~20%

테스트케이스확인