백준 16234 < 인구 이동 > JavaScript

📍문제 링크

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

16234번: 인구 이동

 

📍알고리즘 분류

- 구현
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색
- 시뮬레이션

 

📍문제 풀이

구현할 내용이 엄청 많고 복잡했다..

 

프로그램 동작 기능

1. board를 탐색하여 인구 이동의 가능성이 있으면 인구가 이동될 좌표들 그룹을 구한다

- 인구 이동 가능성은 중첩 for 문을 활용하여 판정

- 인구가 이동될 좌표들 그룹을 구하기 위해 방문/미방문 좌표를 체크하고, 미방문 좌표에 bfs를 실행

- 최종 결과로 그룹을 구함

2. 구해진 그룹을 순회하며 한 묶음의 좌표들에 대해 인구 이동을 실시

3. 반복이 끝나면 timer 출력 

 

📍코드 (JavaScript)

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];
const dy = [-1, 1, 0, 0];
const dx = [0, 0, -1, 1];
const getIsVisited = (N) => {
  return Array.from({ length: N }, (_) =>
    Array.from({ length: N }, (_) => false),
  );
};

// 전체 보드를 순회하면서 아직 인구 이동할 수 있으면 false 리턴
const isEnd = (Map, N, L, R) => {
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      const currentVal = Map[i][j];
      for (let k = 0; k < 4; k++) {
        const newY = i + dy[k];
        const newX = j + dx[k];
        if (newY >= 0 && newX >= 0 && newY < N && newX < N) {
          const newVal = Map[newY][newX];
          const absVal = Math.abs(currentVal - newVal);
          if (absVal >= L && absVal <= R) return false;
        }
      }
    }
  }
  return true;
};

// bfs로 board를 탐색하며 같은 국경이 될 수 있는 좌표 리스트를 반환
const getPosArr = (Map, visitArr, Y, X, N, L, R) => {
  const posArr = [[Y, X]];
  const queue = [[Y, X]];

  while (queue.length) {
    const [currentY, currentX] = queue.shift();

    for (let i = 0; i < 4; i++) {
      const newY = currentY + dy[i];
      const newX = currentX + dx[i];
      if (
        newY >= 0 &&
        newX >= 0 &&
        newY < N &&
        newX < N &&
        !visitArr[newY][newX]
      ) {
        // currentY,X 자리에 그냥 최초 좌표인 Y, X 써서 에러났었음..
        const newVal = Math.abs(Map[currentY][currentX] - Map[newY][newX]);
        if (newVal >= L && newVal <= R) {
          visitArr[newY][newX] = true;
          queue.push([newY, newX]);
          posArr.push([newY, newX]);
        }
      }
    }
  }
  return posArr;
};

// 전체 보드를 탐색하면서 미방문된 좌표에 bfs 실행
const boardScan = (Map, N, L, R) => {
  const Groups = [];
  const isVisited = getIsVisited(N);
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (!isVisited[i][j]) {
        isVisited[i][j] = true;
        const posArr = getPosArr(Map, isVisited, i, j, N, L, R);
        if (posArr.length > 1) Groups.push(posArr);
      }
    }
  }
  return Groups;
};

// 국경 그룹을 받아 전체 보드를 변경하는 함수
const move = (Board, Groups) => {
  for (let posArr of Groups) {
    let sum = 0;
    for (let pos of posArr) {
      sum += Board[pos[0]][pos[1]];
    }
    const newVal = Math.floor(sum / posArr.length);
    for (let pos of posArr) {
      Board[pos[0]][pos[1]] = newVal;
    }
  }
  return Board;
};

rl.on("line", (line) => {
  input.push(line);
}).on("close", () => {
  const [n, l, r] = input.shift().split(" ").map(Number);
  const board = input.map((row) => row.split(" ").map(Number));
  let timer = 0;
  while (true) {
    // LR 체크
    if (isEnd(board, n, l, r)) break;
    timer++;
    const groups = boardScan(board, n, l, r);
    move(board, groups);
  }
  console.log(timer);
});

 

📍리뷰

- 역시 독립된 함수로 선언하니 테스트 하기가 편했다

- 중간에 사소한 오타로 인해 에러가 발생했는데, 에러를 막을 방법을 생각해봐야겠다

독립된 함수의 매개변수는 파스칼 케이스

로컬 변수는 카멜 케이스