백준 16234번: 인구이동(javascript, BFS, 완전탐색)

완전탐색이며 BFS로 풀 수 있는 문제이다. 물론 DFS로도 풀어도 되지만 문제 조건에 인접한 국가만 국경을 열 수 있다는 점에서 넓이 우선 탐색이 좀 더 직관적으로 풀 수 있다고 생각해 BFS로 접근하여 풀었다.

 

예제에서 N이 3이상인, 즉 인구이동이 다른 구역에서 동시에 일어날 때 인구가 어떻게 합쳐지는 지에 대한 설명이 없어 디버깅에 조금 어려움을 겪었던 문제였다. 물론 예제 4,5를 통해 알수는 있지만 그 과정을 일일히 찾기에 어려움이 있었다. 

 

예제 4,5에서 인구이동이 일어나는 과정을 적은 글이 있어 이 문제를 푸는데 어려움을 겪는 사람이 있다면 참고하면 디버깅에 도움이 될 것 같다.  

const fs = require('fs');
const input = fs.readFileSync("/dev/stdin").toString().trim().split('\n');

const [N, L, R] = input[0].split(' ').map(a => Number(a))
const board = Array.from({length: N}, ()=> [])
for(let i=0; i<N; i++){
    board[i] = input[i+1].split(' ').map(a => Number(a))
}

let answer = 0

for(let k=0; k<2001; k++){
    let uni = 0
    let list = []
    visited = Array.from({length: N}, ()=> {})
    for(let _=0; _<N; _++){
        visited[_] = Array.from({length: N}, () => {}).fill(false)
    }

    for(let row=0; row<N; row++){
        for(let col=0; col<N; col++){
            const [cash, sum] = BFS(row,col)
            if(cash.length>1){
                list.push([cash, Math.floor(sum/cash.length)])
                uni++
            }
        }
    }

    for(const li of list){
        for(const l of li[0]){
            board[l[0]][l[1]] = li[1]
        }
    }


    if(uni>0){
        answer++
    }
    else{
        break
    }
}

console.log(answer)

function BFS(r,c){
    const dx = [0, 0, 1, -1]
    const dy = [1, -1, 0, 0]

    let sum = board[r][c]
    let union = [[r,c]]
    let queue = [[r,c]]
    visited[r][c] = true

    while(queue.length){
        const cash = queue.shift()
        for(let i =0; i<4; i++){
            const nrow = cash[0] + dx[i]
            const ncol = cash[1] + dy[i]
            if(0<= nrow && nrow < N && 0 <= ncol && ncol < N && !visited[nrow][ncol] && L <= Math.abs(board[nrow][ncol]-board[cash[0]][cash[1]]) &&
                Math.abs(board[nrow][ncol]-board[cash[0]][cash[1]]) <= R){
                sum += board[nrow][ncol]
                union.push([nrow,ncol])
                queue.push([nrow,ncol])
                visited[nrow][ncol] = true
            }
        }
    }
    return [union, sum]
}