[BOJ] 1012: 유기농 배추 / JS

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

 

 

 

 

const [t, ...input] = require('fs')
  .readFileSync('./input.txt')
  .toString()
  .trim()
  .split('\n');

let n, m;

const dx = [0, 0, 1, -1];
const dy = [1, -1, 0, 0];

function isRange(x, y) {
  return x >= 0 && x < n && y >= 0 && y < m;
}

function bfs(i, j) {
  const queue = [[i, j]];
  map[i][j] = 0;
  while (queue.length) {
    const [x, y] = queue.shift();
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];

      if (!isRange(nx, ny) || map[nx][ny] === 0) continue;
      queue.push([nx, ny]);
      map[nx][ny] = 0;
    }
  }
}

let map;
function mapping(n, m, k) {
  map = new Array(n);
  for (let i = 0; i < n; i++) map[i] = Array.from({ length: m }, () => 0);

  for (let i = 0; i < k; i++) {
    const [x, y] = input.shift().split(' ').map(Number);
    map[y][x] = 1;
  }
}

function solution() {
  for (let a = 0; a < t; a++) {
    const [column, row, k] = input.shift().split(' ').map(Number);
    n = row;
    m = column;
    mapping(n, m, k);

    let num = 0;
    for (let i = 0; i < n; i++) {
      for (let j = 0; j < m; j++) {
        if (map[i][j] === 0) continue;
        bfs(i, j);
        num++;
      }
    }
    console.log(num);
  }
}
solution();

"1021: 유기농 배추"는 배추들이 이어져있는 구역을 세는 문제다.

즉 그래프의 개수를 구하면 된다.

이번 문제도 역시 BFS로 해결할 수 있다.

 

solution 함수를 보면 테스트케이스의 실행 횟수는 t에 받고, 밭에 대한 정보는 input에 담는다.

input에서 제일 앞에 있는 데이터는 밭의 크기와 배추에 대한 정보이므로 shift 멤버 함수로 따로 변수에 담는다.

해당 정보를 이용해서 mapping 함수로 밭에 대한 배열을 만든다.

 

그런 다음 map에 있는 밭에 대한 데이터를 바탕으로 bfs를 호출해서 그래프의 개수를 구하면된다.

bfs 함수는 말그대로 BFS를 수행하는 함수다.

그래프의 첫 시작점을 매개변수로 전달하면 큐에 담아서 시작한다.

큐의 front를 하나씩 꺼내면서 현재 칸에 대한 상하좌우 칸에 대해 검사하고, 배추가 있다면 큐에 담는다.

이때 방문한 칸에 대해서는 map[i][j]을 0으로 할당해서 이후에 재방문했을 때 건너뛸 수 있게 하면 된다.