[백준 1012 - Node.js] 유기농 배추

🔗 문제 링크

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

1012번: 유기농 배추

✏️ 풀이

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const iterator = input[Symbol.iterator]();
const offset = [[0, 1], [1, 0], [0, -1], [-1, 0]];
const output = [];

const dfs = (start, M, N, farm) => {
  const stack = [start];
  while (stack.length) {
    const [x, y] = stack.pop();
    for (let i = 0; i < 4; i++) {
      const nx = x + offset[i][0];
      const ny = y + offset[i][1];
      if (nx >= 0 && nx < M && ny >= 0 && ny < N && farm[nx][ny]) {
        farm[nx][ny] = 0;
        stack.push([nx, ny]);
      }
    }
  }
};

iterator.next();
while (true) {
  const { value, done } = iterator.next();
  if (done) {
    break;
  }
  const [M, N, K] = value.split(' ').map(Number);
  const farm = [...Array(M)].map(() => Array(N).fill(0));
  for (let i = 0; i < K; i++) {
    const [x, y] = iterator.next().value.split(' ').map(Number);
    farm[x][y] = 1;
  }
  let count = 0;
  for (let x = 0; x < M; x++) {
    for (let y = 0; y < N; y++) {
      if (farm[x][y]) {
        farm[x][y] = 0;
        dfs([x, y], M, N, farm);
        count++;
      }
    }
  }
  output.push(count);
}

console.log(output.join('\n'));

입력값으로 여러 개의 테스트 케이스를 동시에 받고 있다. 일단 모든 입력값을 한 줄씩 잘라서 input에 담고, input의 iterator를 활용하여 순회하였다. 먼저 맨 처음 테스트 케이스 개수는 필요 없기 때문에 바로 next()로 넘어가고, 그 다음부터는 테스트 케이스가 시작되는데, 각 테스트 케이스의 첫 번째 줄에서 next()로 M, N, K를 얻어내고, 그 다음에는 K개 만큼의 줄이 하나의 테스트 케이스이므로 K번 next()를 호출하였다.

 

farm에 0으로 초기화한 2차원 배열을 만들어 저장하고, K줄의 배추 좌표 정보를 통해 배추가 심어진 위치를 1로 갱신한다. 그 다음, farm을 순회하면서 배추가 심어진 좌표가 나올 때마다 해당 좌표를 배추가 없는 칸(0)으로 갱신하고 dfs를 실행한다. dfs를 실행할 때에도 마찬가지로 배추가 있는 좌표를 모두 탐색하고 탐색을 마친 칸은 0으로 갱신한다. 이렇게 하면 dfs를 실행할 때마다 dfs를 시작한 좌표와 인접한 모든 배추가 있는 좌표를 0으로 갱신하게 되는데, 이 때 탐색한 배추가 있는 좌표는 배추흰지렁이가 시작 좌표에서 이동할 수 있는 모든 배추와 같다. 따라서 dfs를 실행한 횟수가 곧 필요한 배추흰지렁이의 마리수가 된다.

 

farm을 1회 순회하면서 dfs를 실행한 횟수를 output에 push하고, 모든 테스트 케이스를 전부 다 확인한 후에 최종적으로 output을 개행 문자로 이어붙여서 출력하였다.

 

 

🗃️ 다른 언어로 된 풀이

[백준 1012] 유기농 배추 with Python