[JS] 백준 2573 : 빙산

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

2573번: 빙산

 

📋풀이방법

1. 빙하가 2개이상 되거나 0개일 때까지 반복

2. 먼저 빙산정보를 따로 깊은복사함

  -> 위에서부터 순서대로 순회하기때문에 한번에 녹는 방식과 다르다

  ->그러므로 미리 복사를 해놓아서 복사해놓은 배열을 기준으로 원본배열의 빙산을 녹여야한다.

3. 순서대로 0이 아닌 빙산이 있는 곳을 검사한다.

4. 빙산이 있다면 4방향에 0이 있는지 확인하고 있다면 1씩 빼준다.

5. 다시 위에서부터 순회하면서 0이 아닌 곳을 찾는다.

6. 0이아닌 곳을 찾으면 DFS로 순회한다.

 -이때 그 지점은 빙산 한 덩어리를 뜻한다(cnt++)

7.DFS로 순회하면서 방문한곳은 visited에 표시해준다.

8.DFS가 끝나면 그 빙산은 한덩어리를 뜻한다.

 

 

 

내 제출

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 [N,M]=input.shift().split(" ").map(Number);

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


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

let answer=0;
while(1){
    let temp=arr.map(x=>[...x])
    for(var i=0;i<N;i++){
        for(var j=0;j<M;j++){
                if(temp[i][j]!=0){
                    for(var k=0;k<4;k++){
                        let nx=j+dx[k];
                        let ny=i+dy[k];
                        if(nx>=0&&ny>=0&&nx<M&&ny<N){
                            if(temp[ny][nx]==0 && arr[i][j]>0){
                                arr[i][j]-=1;
                            }
                            
                        }
                    }
                }
        }
    }
    answer++;
    let visited=Array.from({length:N},()=>Array(M).fill(0));
    function DFS(y,x){
        for(var i=0;i<4;i++){
            let nx=x+dx[i];
            let ny=y+dy[i];
            if(nx>=0&&ny>=0&&nx<M&&ny<N && arr[ny][nx]!=0){
                if(visited[ny][nx]==0){
                    visited[ny][nx]=1;
                    DFS(ny,nx)
                }
            }
        }
    }
    let cnt=0;
    for(var i=0;i<N;i++){
        for(var j=0;j<M;j++){
            if(arr[i][j]!=0 && visited[i][j]==0){
                visited[i][j] = 1;
                DFS(i,j)
                cnt++
            }
        }       
    }
    console.log(arr.join("\n"))
    console.log("\n")
    if(cnt>=2) break;
    if(cnt==0) {
        answer=0;
        break;
    }

}
console.log(answer)

 

 

💢어려웠던 점

1. 30분이내로 풀어서 어렵진 않았다.

2. 먼저 빙산의 정보를 따로 깊은복사하는 방법을 안해서 오답이나왔다.

 -복사한 배열이 없으면 위에서부터 순서대로 순회하기 때문에 0이되는 곳이 생기면 그 뒤에 빙산에도 영향을 주게된다.