[BaekJoon] 16234 번 인구 이동 문제 - (nodejs)

문제 번호 :  16234번

문제 바로가기 ☞ https://www.acmicpc.net/problem/16234

---

 

<<< 문제 내용 >>>

---

 

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

const [N, L, R] = input[0].split(" ").map(Number);
// 정사각형 땅
const array = [];
// 몇번이나 이동했는지
let moveCount = 0;

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

const dy = [-1, 1, 0, 0];
const dx = [0, 0, -1, 1];
// 이동이 생긴 땅 좌표
let locations = [];
// 그룹 별 합
let groupValue = [];
// 현재 묶이는 그룹의 번호를 위한 변수
let group = 0;

const bfs = (y, x, visited) => {
  let queue = [[y, x]];
  visited[y][x] = true;
  let sum = array[y][x];
  let count = 1;
  let loc = [];

  while (queue.length) {
    const [y, x] = queue.shift();
    loc.push([y, x, group]);

    for (let i = 0; i < 4; i++) {
      const ny = y + dy[i];
      const nx = x + dx[i];

      if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;

      const value = Math.abs(array[y][x] - array[ny][nx]);

      if (!visited[ny][nx] && value >= L && value <= R) {
        queue.push([ny, nx]);
        sum += array[ny][nx];
        count++;
        visited[ny][nx] = true;
      }
    }
  }
  
  /* 그냥 들리기만 한 것이 아니라 이동 행위를 했을 시에만
  그룹별로 땅을 묶어주는 작업을 시행 */

  if (loc.length > 1) {
    for (const d of loc) {
      locations.push(d);
    }
  }

  if (count > 1) {
    groupValue.push(Math.floor(sum / count));
    group++;
  }
};

while (true) {
  let visited = Array.from(Array(N), () => new Array(N).fill(false));
  locations = [];
  groupValue = [];
  group = 0;

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (!visited[i][j]) {
        bfs(i, j, visited);
      }
    }
  }

  // 연합되는 땅이 없다면 종료
  if (locations.length === 0) {
    console.log(moveCount);
    break;
  }

  // 연합되는 땅을 꺼내서 기존 땅의 인원수를 조절
  while (locations.length) {
    const [y, x, l] = locations.pop();

    array[y][x] = groupValue[l];
  }

  moveCount++;
}

 

 

도움이 되셨다면 공감 부탁드립니다.