[JS] 백준 16234번 : 인구이동

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

16234번: 인구 이동

 

📋풀이방법

1. 상하좌우 검사 L명이상 R명이하인지

2. DFS를 통해 연합배열에 삽입, visited활성화로 중복 탐색 방지

3. 연합배열안에 든 좌표끼리 연합공식으로 인구수를 나눠서 넣음

4. 다시 처음([0,0]) 나라부터 검사 -인구수가 바뀌었으니까

 

 

🤟내 제출

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 t_arr=input.shift().split(" ").map(Number);
let N=t_arr[0];
let L=t_arr[1];
let R=t_arr[2];

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 visited =Array.from({length:N},()=>Array(N).fill(0))
    let Union=[];
    for(var i=0;i<N;i++){
        for(var j=0;j<N;j++){
            if(visited[i][j]==0){
                let temp=[];
                function DFS(D,y,x){
                    for(var z=0;z<4;z++){
                        let nx=x+dx[z];
                        let ny=y+dy[z];
                        if(nx>=0&&ny>=0&&nx<N&&ny<N &&visited[ny][nx]==0){
                            let num=Math.abs(arr[ny][nx]-arr[y][x]);
                            if(num>=L && num<=R){
                                visited[ny][nx]=1;
                                temp.push([ny,nx,arr[ny][nx]])
                                DFS(L+1,ny,nx)
                            }
                            
                        }
                    }
                }
                visited[i][j]=1;
                temp.push([i,j,arr[i][j]])
                DFS(0,i,j);
                if(temp.length>1) Union.push(temp);
            }
            
        }
    }
    if(Union.length==0) break;
    Union.forEach((area)=>{
        let sum=area.reduce((a,c)=>a+c[2],0)
        area.forEach((t_area)=>{
            let [ay,ax,peo]=t_area;
            let go=Math.floor(sum/area.length);
            arr[ay][ax]=go
        });
        
    })
    answer++;
}
console.log(answer)

 

 

📝추가적인 부분

1. 한번에 문제를 맞췄다.

2. 푸는 시간은 약 50분 걸렸다.

3.어려웠던 부분이 없었다.