[Node.js] 16234_인구 이동

문제

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

 

풀이

이 문제는 BFS를 학습하기 위해 풀어본 문제이며 이 문제를 통해 BFS를 조금 알기 시작했다....

 

문제에서는 각 칸마다 연합을 연결할 수 있는 나라인지 확인한 뒤 계속 인접 칸으로 이동해야 한다. 이러한 풀이 방식에서 인접 노드 탐색을 진행하는 BFS를 적용해야한다.

 

bfs 함수를 실행하는 이중 for문은 각 칸마다 연합을 만들 수 있는지 검증하는 경우를 구현하기위해 사용했고, 해당 노드가 방문했던 노드임을 나타내는 visited 배열을 생성했으며 이 배열을 bfs 함수에 전달해 함수 내부에서 방문 여부를 확인해 방문 하지 않고, 함수에서는 상하좌우 방향의 노드와 현 위치의 노드 간의 차이가 문제에서 주어진 범위 안에 있다면 que에 push해 다음 동작을 할 노드를 추가한다.

 

이후 연합된 나라의 수를 측정해 처음 시작한 나라만 있으면 연합으로 연결되지 않았음을 의미하기 때문에 false를 반환해 연합되지 않았음을 나타내는 isUnion 변수에 false값이 되게 한다. 만약 연합이 되는 노드였다면 isUnion은 true값을 갖게 될 것이다.

 

이 문제에서는 탐색을 하는 것도 중요하지만 visited 즉, 방문 여부를 전달해 동작의 최적화가 중요했던 문제인거 같다.

 

코드

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt')
  .toString().trim().split('\n').map(e => e.split(' ').map(Number));

const [n, min, max] = input.shift();
let map = input.slice();
const dir = [[-1, 0], [1, 0], [0, -1], [0, 1]];

let answer = 0;

const bfs = (y, x, visited) => {
  // 연합을 연결할 수 있는지 확인
  let union = [[y, x]];
  let que = [[y, x]];
  let sum = map[y][x];
  visited[y][x] = true;

  while (que.length > 0) {
    const [cY, cX] = que.shift();
    const cNum = map[cY][cX];

    for (let i = 0; i < 4; i++){
      const [dY, dX] = dir[i];
      const nY = cY + dY;
      const nX = cX + dX;

      if (nY >= n || nY < 0 || nX >= n || nX < 0 || visited[nY][nX]) continue;
      else if (Math.abs(cNum - map[nY][nX]) >= min && Math.abs(cNum - map[nY][nX]) <= max && !visited[nY][nX]) {
        que.push([nY, nX]);
        union.push([nY, nX]);
        sum += map[nY][nX];
        visited[nY][nX] = true;
      }
    }
  }
  if (union.length === 1) return false;
    else {
      const population = Math.floor(sum / union.length);
      union.forEach(e => {
        map[e[0]][e[1]] = population;
      })
      return true;
    }
}
while (true) {
  let visited = Array.from(Array(n), () => Array(n).fill(false));
  let isUnion = false;
  for (let i = 0; i < n; i++){
    for (let j = 0; j < n; j++){
      if (visited[i][j] === false && bfs(i, j, visited)) {
        isUnion = true;
      }
    }
  }
  if (!isUnion) break;
  answer += isUnion ? 1 : 0;
}

console.log(answer)