[백준] 2667번 : 단지번호붙이기 (실버Ⅰ) by node.js

▷ 문제 : 2667번 - 단지지번호붙이기

2667번: 단지번호붙이기

▷ 해결 날짜 : 2022.04.07
▷ 소요 시간 : 30분
▷ 풀이 과정 :

1012번 - 유기농 배추 문제와 매우 유사해서 그냥 유사하게 풀어버렸다.

1로 이루어진 집단의 개수와, 집단 안에 존재하는 1의 개수를 오름차순으로 출력하는 문제였다.

 

유기농 배추 문제와 유사한 방향으로 풀었고 이 문제에 맞게 조금 수정을 해서 사용하였다.

 

▷ 구현

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().split('\n');

const ds = [[-1, 0], [1, 0], [0, 1], [0, -1]];
let graph = [], results = [], size = 0;

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

const search = (startX, startY) => {
  let result = 0;
  const queue = [[startX, startY]];
  while(queue.length){
    const [x, y] = queue.shift();
    if(!graph[x][y]) continue;
    
    graph[x][y] = 0;
    result++;

    for(let i = 0; i < 4; i++){
      const xPos = x + ds[i][0];
      const yPos = y + ds[i][1];

      if(xPos < 0 || yPos < 0 || xPos >= size || yPos >= size) continue;
      if(graph[xPos][yPos]) queue.push([xPos, yPos]);
    }
  }

  results.push(result);
};

size = Number(input.shift());

graph = [...Array(size)];
for(let i = 0 ; i < input.length ; i++){
  graph[i] = [...input[i].replace(/\r/g,'').split('').map(Number)];
}

solution();
console.log(results.length);
results.sort((a, b) => a - b).forEach( e => {
  console.log(e);
});

 

▷ 복기 :

다른 사람 코드도 크게 다를건 없지만 저 search 부분을 나는 그냥 상하좌우 queue, while, for문을 통해 구현했는데, 많은 사람들이 재귀를 통해 구현했다.

 

다음번엔 재귀를 통해서도 구현해봐야겠다.