[백준] 1012번 : 유기농 배추 (실버Ⅱ) by node.js

▷ 문제 :1012번 : 유기농 배추

1012번: 유기농 배추

▷ 해결 날짜 : 2022.04.06
▷ 소요 시간 : 2시간
▷ 풀이 과정 :

주어지는 값은 테스트 케이스, 배추밭의 가로, 세로의 길이 그리고 배추가 심어져 있는 위치가 주어진다.

문제를 보면 이미지가 첨부되어 있어 쉽게 이해할 수 있도록 도움을 주는데,

결국 인접하고 있는 배추묶음을 하나로 보고 그 묶음의 개수를 세는 것이다. (문제는 배추흰지렁이의 개수를 출력하는 것이지만...)

 

우선 풀이 순서의 큰 틀을 다음과 같이 정하고 구현하였다.

1. 테스트 케이스 만큼 반복
2. 각 테스트 케이스 별 그래프(배추밭) 생성
3. 배추밭에 배추 삽입
4. 전체 탐색하면서 상하좌우 인접배열 탐색
5. 개수 출력
6. 다음 테스트 케이스 실행

 

▷ 구현

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, xMax, yMax, c;
let tc = Number(input.shift());

// 삽입 지렁이 개수 확인
const putWorms = () => {
  let result = 0;
  for(let i = 0 ; i < yMax ; i++){
    for(let j = 0 ; j < xMax ; j++){
      if(graph[i][j]) {
        bfs(i, j);
        result++;
      }
    }
  }
  console.log(result);
}

// 반복
const bfs = (startX, startY) => {
  const queue = [[startX, startY]];
  while(queue.length){
    const [x, y] = queue.shift();
    if(!graph[x][y]) continue;
    else graph[x][y] = 0;

    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 >= yMax || yPos >= xMax) continue;
      if(graph[xPos][yPos]) queue.push([xPos, yPos]);
    }
  }
};

for(let i = 0 ; i < tc ; i++){
  [xMax, yMax, c] = input.shift().split(' ').map(Number);

  // 그래프 생성
  graph = [...Array(yMax)].map(e => Array(xMax).fill(0));

  // 배추 삽입
  for(let j = 0 ; j < c; j++){
    let [cx, cy] = input[j].split(' ').map(Number);
    graph[cy][cx] = 1;
  }

  // 배추흰지렁이 개수 확인
  putWorms();

  // next test case
  input = input.slice(c);
}

 

▷ 복기 :

상당히 오래 걸렸는데, 내가 상하좌우 탐색이 매우 약하다는걸 알게됐다.

이 문제를 기점으로 여러 케이스를 풀어봐야지;