[알고리즘 연습] 백준 2667 (단지번호붙이기, 자바스크립트)

문제

2667번: 단지번호붙이기

---

풀이

• 2중 for문으로 값이 1인 위치를 찾는다. 이 때 총 단지수를 1증가시키고 해당 위치에서 시작하는 BFS를 수행한다.
• BFS를 통해 방문할 수 있었던 위치의 수를 반환한다.
• 한 번 방문한 위치는 다시는 방문할 수 없도록 값을 0으로 변경한다.

소스 코드

class Queue {
  constructor() {
    this.data = [];
    this.head = 0;
    this.tail = 0;
  }

  push(item) {
    this.data[this.tail++] = item;
  }

  pop() {
    this.head++;
  }

  front() {
    return this.data[this.head];
  }

  rear() {
    return this.data[this.tail - 1];
  }

  isEmpty() {
    return this.head === this.tail;
  }

  size() {
    return Math.abs(this.head - this.tail);
  }
}

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

const N = +input[0];
const map = Array.from({ length: N }, () => Array(N).fill(0));
let result = 0;
let answer = [];
const dir = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1],
];

for (let i = 1; i <= N; i++) {
  const temp = input[i].split("").map((el) => +el);
  for (let j = 0; j < N; j++) {
    map[i - 1][j] = temp[j];
  }
}

for (let i = 0; i < N; i++) {
  for (let j = 0; j < N; j++) {
    if (map[i][j] === 0) continue;

    result += 1;
    answer.push(dfs(i, j));
  }
}

answer.sort((a, b) => a - b);
console.log(result);
console.log(answer.join("\n"));

function dfs(i, j) {
  const queue = new Queue();
  let count = 1;

  queue.push([i, j]);
  map[i][j] = 0;

  while (!queue.isEmpty()) {
    const [x, y] = queue.front();
    queue.pop();

    for (let k = 0; k < 4; k++) {
      const nx = x + dir[k][0];
      const ny = y + dir[k][1];

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

      map[nx][ny] = 0;
      queue.push([nx, ny]);
      count += 1;
    }
  }

  return count;
}