백준 16234: 인구 이동 - javascript(bfs)

문제 출처 

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

 

정답 풀이 

bfs 알고리즘을 활용했다. 

 

- 일단 주어진 board의 전체를 돈다. 

  - 이때 한번 방문한 위치는 안간다.

  - 모든 board를 다 돌았을 때 그 어떤 값도 변경되지 않는다면 반복문에서 break를 한다. 

 

- 한번 방문한 곳에서 bfs 함수를 돌린다.  

  - 이때 arr 배열에 조건에 맞는 (L 이상 R이하 차이) 위치들을 push 한다. 

 

- arr의 위치들의 board 값을 다 더하고 평균을 내서 새롭게 board에 값을 넣어준다.  

정답 코드 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n')
const [n, L, R] = input.shift().split(' ').map(v => +v); 
const board = []; 
for(let i=0; i<n; i++){
    board.push(input[i].split(' ').map(v => +v)); 
}

function solution(n, L, R, board){
    let answer = 0; //인구 이동 며칠?
    const dx = [-1,1,0,0]; 
    const dy = [0,0,-1,1]
    
    while(true){
        let isMoved = false; //하루날에 인구 이동 표시 
        const checked = Array.from({length: n}, () =>new Array(n).fill(false)) //매일 checked 초기화 
        
        //board 그래프 다 돌 것임. 
        for(let i=0; i<n; i++){
          for(let j=0; j<n; j++){
              if(!checked[i][j]){//방문하지 않은 위치
                  let arr = [] //해당 위치랑 조건에 맞는 위치를 넣을 것임. 
                  bfs(i, j, board, checked, arr)
                  
                  if(arr.length <= 1) continue; //arr에 2가지 이상의 위치가 있지 않으면 인구 이동이 없는 것.
                  isMoved = true; //인구 이동 ok 
       
                  let total = arr.reduce((sum,[r,c]) => sum + board[r][c],0) //전체 합 
                  let value = Math.floor(total/arr.length) //평균 
           
                   for(let [r, c] of arr){ //board 각 위치에 새로운 값 넣기 
                         board[r][c] = value
                    }
                 }
             }
          }
        if(!isMoved) break; //인구 이동이 없다면 반복문 break
        answer++; //인구 이동이 있을 때 
    }
    
    return answer; 
    
    function bfs(x, y, board, checked, arr){
        const queue = [[x,y, board[x][y]]]
        checked[x][y] = true
        arr.push([x,y])
        
        while(queue.length){
             let [curX, curY, people] = queue.shift()
             
              for(let d=0; d<4; d++){
                  let nx = curX + dx[d]; 
                  let ny = curY + dy[d]; 
                 
                  if(nx < 0 || ny <0 || nx>= n || ny >= n) continue;
                  if(checked[nx][ny]) continue; 
                  //문제에서 주어진 조건 
                  if(Math.abs(people - board[nx][ny]) < L || Math.abs(people - board[nx][ny]) > R )continue; 
                  
                  checked[nx][ny] = true; 
                  queue.push([nx, ny, board[nx][ny]])
                  arr.push([nx, ny])
                 }
              }
    }
}

console.log(solution(n, L, R, board))