[백준 | 실버 2 | JavaScript] 1012번, 유기농 배추

 

Link

1012번 - 유기농 배추

 

---

문제

풀이

(1) DFS 재귀

let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");

let idx = 0;
const T = Number(input[idx++]);

const dn = [0, 1, 0, -1];
const dm = [1, 0, -1, 0];
const answer = Array.from({ length: T }, () => 0);

for (let t = 0; t < T; t++) {
  const [M, N, K] = input[idx++].split(" ").map(Number);
  const map = Array.from({ length: N }, () =>
    Array.from({ length: M }, () => false)
  );
  const visited = Array.from({ length: N }, () =>
    Array.from({ length: M }, () => false)
  );

  const checked = (n, m) => {
    return n < 0 || m < 0 || n >= N || m >= M;
  };

  const dfs = (n, m) => {
    visited[n][m] = true;

    for (let d = 0; d < 4; d++) {
      const tn = n + dn[d];
      const tm = m + dm[d];

      if (checked(tn, tm)) continue;
      if (!map[tn][tm]) continue;
      if (visited[tn][tm]) continue;

      dfs(tn, tm);
    }
  };

  for (let k = 0; k < K; k++) {
    const [m, n] = input[idx++].split(" ").map(Number);
    map[n][m] = true;
  }

  for (let n = 0; n < N; n++) {
    for (let m = 0; m < M; m++) {
      if (!map[n][m]) continue;
      if (visited[n][m]) continue;

      dfs(n, m);
      answer[t] += 1;
    }
  }
}

answer.map((item) => console.log(item));

(2) BFS

let input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");

let idx = 0;
const T = Number(input[idx++]);

// 0: 오른쪽, 1: 아래, 2: 왼쪽, 3: 위
const dn = [0, 1, 0, -1];
const dm = [1, 0, -1, 0];
const answer = Array.from({ length: T }, () => 0);

for (let t = 0; t < T; t++) {
  const [M, N, K] = input[idx++].split(" ").map(Number);
  const map = Array.from({ length: N }, () =>
    Array.from({ length: M }, () => false)
  );
  const visited = Array.from({ length: N }, () =>
    Array.from({ length: M }, () => false)
  );

  const checked = (n, m) => {
    return n < 0 || m < 0 || n >= N || m >= M;
  };

  const bfs = (n, m) => {
    const queue = [];

    queue.push([n, m]);
    visited[n][m] = true;

    while (queue.length > 0) {
      const [qn, qm] = queue.shift();

      console.log(qn, qm);

      for (let d = 0; d < 4; d++) {
        const tn = qn + dn[d];
        const tm = qm + dm[d];

        if (checked(tn, tm)) continue;
        if (visited[tn][tm]) continue;
        if (!map[tn][tm]) continue;

        visited[tn][tm] = true;

        queue.push([tn, tm]);
      }
    }
  };

  for (let k = 0; k < K; k++) {
    const [m, n] = input[idx++].split(" ").map(Number);
    map[n][m] = true;
  }

  for (let n = 0; n < N; n++) {
    for (let m = 0; m < M; m++) {
      if (!map[n][m]) continue;
      if (visited[n][m]) continue;

      bfs(n, m); // 배추 땅
      answer[t] += 1;
    }
  }
}

answer.map((item) => console.log(item));