유기농 배추

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다. 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다. 두 배추의 위치가 같은 경우는 없다.

출력

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

풀이

class Node {
  constructor(data, prev = null, next = null) {
    this.data = data;
    this.prev = prev;
    this.next = next;
  }
}

class Queue {
  constructor() {
    this.head = new Node(-1);
    this.tail = new Node(-1);
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.size = 0;
  }
  enQueue(data) {
    let node = new Node(data);
    node.next = this.tail;
    node.prev = this.tail.prev;
    this.tail.prev.next = node;
    this.tail.prev = node;
    this.size++;
  }
  deQueue() {
    if (this.ifEmpty()) return -1;
    let tmp = this.head.next;
    this.head.next = tmp.next;
    tmp.next.prev = this.head;
    this.size--;
    return tmp.data;
  }
  ifEmpty() {
    return this.size ? false : true;
  }
}

const memset = (arr) => {
  for (let i = 0; i < 50; i++) {
    for (let j = 0; j < 50; j++) {
      arr[i][j] = 0;
    }
  }
};

const cabbage = () => {
  let input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map((n) => n.split(" ").map(Number));
  let i = 1;
  const len = input.length;
  const dir = [
    [1, 0, -1, 0],
    [0, 1, 0, -1],
  ];
  let arr = Array(50);
  for (let j = 0; j < 50; j++) {
    arr[j] = Array.from({ length: 50 }, (v) => 0);
  }
  while (i < len) {
    let m = input[i][0];
    let n = input[i][1];
    let k = input[i++][2];
    let island = 0;
    let queue = new Queue();
    while (k--) {
      arr[input[i][0]][input[i][1]]++;
      i++;
    }
    for (let j = 0; j < m; j++) {
      for (let l = 0; l < n; l++) {
        if (arr[j][l] === 1) {
          queue.enQueue([j, l]);
          arr[j][l] = 2;
          while (!queue.ifEmpty()) {
            let cur = queue.deQueue();
            for (let a = 0; a < 4; a++) {
              let coord = [cur[0] + dir[0][a], cur[1] + dir[1][a]];
              if (
                coord[0] < 0 ||
                coord[0] >= m ||
                coord[1] < 0 ||
                coord[1] >= n
              )
                continue;
              if (arr[coord[0]][coord[1]] !== 1) continue;
              queue.enQueue([coord[0], coord[1]]);
              arr[coord[0]][coord[1]] = 2;
            }
          }
          island++;
        }
      }
    }
    console.log(island);
    memset(arr);
  }
};

cabbage();

반성회

뭔가 비효율적으로 보이지만 ㅡ,,ㅡ;;

테스트케이스가 여러 개 들어오다보니 for문을 좀 자주 쓰게되는것같다

저작자표시