[baekjoon] #1012 유기농 배추 (Node.js)

📖 문제

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

☃️ 풀이

먼저 tc와 m, n, k를 뽑아낸 뒤 문제를 해결하기 위해 배추밭field 세팅을 한다.

이제 배추밭 격자에 대해 순회를 돌며 배추가 있는 칸, 즉 field[y][x] === 1인 곳에서 search 함수를 실행한다.

search 함수는 입력 받은 좌표의 상하좌우를 탐색하며 배추가 있는 곳을 찾는다. 배추가 있다면 해당 좌표의 값을 2로 갱신하고 해당 위치에서 다시 search 함수를 호출한다. 인접한 곳에 배추가 있는 땅이 더 이상 없다면 다음 좌표를 탐색하며 배추가 있는 칸을 찾는다.

이 때, 이미 방문한 배추가 있는 땅의 값은 2로 갱신되었기 때문에 해당 단계에서 탐색되지 않는다.

위와 같은 과정을 반복하며 배추가 있는 땅을 방문할 때마다 cnt에 1씩 더하고, 탐색이 끝나면 cnt를 반환해준다.

--

그래프 탐색은 개인적으로 어렵다고 느끼는, 그리고 동시에 굉장히 재밌다고 생각하는 유형 중 하나이다. 다른 문제들과는 다르게 탐색해나가는 과정을 이미지화 하여 머리속으로 떠올리기 때문인 듯 하다.

아무튼, 높은 난이도의 문제는 아니었지만 스스로의 힘으로 해결하여 더욱 뿌듯함을 느끼게 해준 문제였음.

💽 소스코드

const input = require('fs').readFileSync('input.txt').toString().split('\n');
const tc = Number(input.shift());
const dxs = [0, 1, 0, -1];
const dys = [1, 0, -1, 0];

for (let t = 0; t < tc; t++) {
  const [m, n, k] = input.shift().split(' ').map(Number);
  const field = Array.from({ length: n }, () =>
    Array.from({ length: m }, () => 0)
  );
  let cnt = 0;

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

    field[y][x] = 1;
  }

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (field[i][j] === 1) {
        search(j, i);
        cnt++;
      }
    }
  }

  console.log(cnt);

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

  function search(x, y) {
    field[y][x] = 2;

    for (let d = 0; d < 4; d++) {
      const nx = x + dxs[d];
      const ny = y + dys[d];

      if (in_range(nx, ny) && field[ny][nx] === 1) search(nx, ny);
    }
  }
}