백준 js 2667번

<문제>

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

 

 

 

<문제 핵심>

 

1. bfs

✅ 위치를 기준으로 상,하,좌,우 숫자 1이 있는지를 파악해야 되기 때문에 bfs 알고리즘을 활용한다. 

 

<문제 풀이과정 및 순서도>

1. 입력 받은 후 배열의 크기, 집들이 있는 2차원 배열, 각 단지를 담는 배열, 그리고 상,하,좌,우로 움직이기 위한 방향 벡터 배열을 생성한다. 

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

let size = Number(input.shift());
let houses = input.map((row) => row.split("").map((num) => +num));
let housesByNeighborhood = [];

const dirs = [
  [-1, 0], // 상
  [1, 0], // 하
  [0, -1], // 좌
  [0, 1], // 우
];

 

2. 만든 houses 배열을 탐색하면서 bfs함수를 호출한다. 이후 단지 정보가 담긴 배열을 오름차순 정렬하고 단지 정보의 수, 그리고 각 단지의 크기를 출력한다.

const solution = () => {
  for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
      if (houses[i][j]) bfs(i, j);
    }
  }

  // 단지의 크기를 오름차순으로 정렬
  housesByNeighborhood.sort((a, b) => a - b);

  // 총 단지 수 출력
  console.log(housesByNeighborhood.length);

  // 각 단지의 크기 출력
  housesByNeighborhood.forEach((size) => console.log(size));
};

 

3. bfs함수 로직을 구현한다.

✅ 방문 한 후 재방문을 방지하고 result를 1개 증가시킨다. 

✅ 이동하면서 유효조건을 위배하지 않는다면 queue에 넣고 다시 방문처리한다.

const bfs = (startX, startY) => {
  let result = 0;
  const queue = [[startX, startY]];

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

    // 이미 방문한 위치라면 건너뜀
    if (houses[x][y] === 0) continue;

    // 방문 표시 및 집의 수 증가
    houses[x][y] = 0;
    result += 1;

    // 상하좌우 방향으로 탐색
    for (let dir of dirs) {
      const xPosition = x + dir[0];
      const yPosition = y + dir[1];

      if (
        xPosition < 0 ||
        yPosition < 0 ||
        xPosition >= size ||
        yPosition >= size
      )
        continue;

      // 집이 있는 위치를 큐에 추가
      if (houses[xPosition][yPosition]) queue.push([xPosition, yPosition]);
    }
  }

  // 하나의 단지 크기를 배열에 추가
  housesByNeighborhood.push(result);
};

 

 

<전체 코드>

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

let size = Number(input.shift());
let houses = input.map((row) => row.split("").map((num) => +num));
let housesByNeighborhood = [];

const dirs = [
  [-1, 0], // 상
  [1, 0], // 하
  [0, -1], // 좌
  [0, 1], // 우
];

const solution = () => {
  for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
      if (houses[i][j]) bfs(i, j);
    }
  }

  // 단지의 크기를 오름차순으로 정렬
  housesByNeighborhood.sort((a, b) => a - b);

  // 총 단지 수 출력
  console.log(housesByNeighborhood.length);

  // 각 단지의 크기 출력
  housesByNeighborhood.forEach((size) => console.log(size));
};

const bfs = (startX, startY) => {
  let result = 0;
  const queue = [[startX, startY]];

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

    // 이미 방문한 위치라면 건너뜀
    if (houses[x][y] === 0) continue;

    // 방문 표시 및 집의 수 증가
    houses[x][y] = 0;
    result += 1;

    // 상하좌우 방향으로 탐색
    for (let dir of dirs) {
      const xPosition = x + dir[0];
      const yPosition = y + dir[1];

      if (
        xPosition < 0 ||
        yPosition < 0 ||
        xPosition >= size ||
        yPosition >= size
      )
        continue;

      // 집이 있는 위치를 큐에 추가
      if (houses[xPosition][yPosition]) queue.push([xPosition, yPosition]);
    }
  }

  // 하나의 단지 크기를 배열에 추가
  housesByNeighborhood.push(result);
};

// 솔루션 실행
solution();