[알고리즘/백준/2667] 단지 번호 붙이기

문제

---

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

2667번: 단지번호붙이기

 

풀이

---

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 fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [N, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");

const n = +N;
const board = arr.map((row) => row.split("").map(Number));
const dx = [-1, 0, 1, 0];
const dy = [0, 1, 0, -1];
const answer = [];

for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (board[i][j] === 1) {
      const q = new Queue();
      q.push([i, j]);
      board[i][j] = 0;
      let cnt = 1;

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

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

          if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] === 1) {
            board[nx][ny] = 0;
            q.push([nx, ny]);
            cnt += 1;
          }
        }
      }

      answer.push(cnt);
    }
  }
}
answer.sort((a, b) => a - b);
console.log([answer.length, ...answer].join("\n"));

board를 순회하며 각 단지가 있는 곳(if (board[i][j])===1)을 먼저 찾는다.

각 단지를 BFS로 탐색하면서 집의 개수를 cnt에 1씩 더해 저장하고, 단지 전체가 구해지면 answer 배열에 값을 저장한다. 

 

시작점인 board[i][j]를 큐에 넣고, board로 방문 표시를 한 다음 cnt를 1 증가시킨다. 

현재 지점을 기준으로 4방향을 탐색하면서 이동 가능한 지점인 경우 같은 작업을 수행한다. 

 

오름차순으로 집 개수를 구하라고 했기 때문에 sort를 통해 오름차순 정렬해준다. 

마지막으로 배열 값을 개행('\n')을 구분자로 join해 답을 구한다.