백준 16637 괄호 추가하기 (node.js)

문제

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

문제 해석

이 문제는 그래프 이론 카테고리에 있으며 BFS로 풀 수 있다.

2중 반복문을 통해 모든 배열을 순회 하지만 그 위치에 집이 있는경우 BFS를 통해 먼저 값을 정답 배열에 추가해주고, grid 값을 0으로 바꿔주면 된다.

 

풀이

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

function solution(input) {
  const N = Number(input.shift());
  const grid = input.map((v) => v.split("").map(Number));
  const answer = [];
  const ds = [
    [-1, 0],
    [1, 0],
    [0, 1],
    [0, -1],
  ];

  const bfs = (start) => {
    const queue = [start];
    let cnt = 0;

    while (queue.length) {
      const [curY, curX] = queue.shift();
      cnt++;

      for (let i = 0; i < 4; i++) {
        const ny = curY + ds[i][1];
        const nx = curX + ds[i][0];

        if (ny >= 0 && ny < N && nx >= 0 && nx < N && grid[ny][nx]) {
          grid[ny][nx] = 0;
          queue.push([ny, nx]);
        }
      }
    }
    return cnt;
  };

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
      if (grid[i][j]) {
        grid[i][j] = 0;
        answer.push(bfs([i, j]));
      }
    }
  }
  answer.sort((a, b) => a - b);
  answer.unshift(answer.length);

  return answer;
}

console.log(solution(input).join("\n"));

 

 

끝