1012.md

유기농 배추

문제

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

정답

let [t, ...list] = require("fs")
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "./input.txt")
  .toString()
  .split("\n");

// dfs 탐색
function dfs(graph, n, m, x, y) {
  // 범위를 벗어나면 종료
  if (x <= -1 || x >= n || y <= -1 || y >= m) {
    return false;
  }
  if (graph[x][y] === 1) {
    // 다음 탐색을 위해 방문한 곳은 -1로 변경
    graph[x][y] = -1;
    // 상하좌우 탐색
    dfs(graph, n, m, x - 1, y);
    dfs(graph, n, m, x, y - 1);
    dfs(graph, n, m, x + 1, y);
    dfs(graph, n, m, x, y + 1);
    return true;
  }
  return false;
}

// 테스트 케이스가 여러개 일 경우 시작할 위치 지정
let line = 0;

// 테스트 케이스 만큼 반복
while (t--) {
  let [m, n, k] = list[line].split(" ").map(Number);
  // 그래프 생성
  let graph = Array.from({ length: +n }, () => new Array(+m).fill(0));

  for (let i = 0; i < k; i++) {
    let [y, x] = list[line + i + 1].split(" ").map(Number);
    graph[x][y] = 1;
  }

  let answer = 0;
  // 그래프 탐색
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (dfs(graph, n, m, i, j)) answer++;
    }
  }

  line += k + 1;
  console.log(answer);
}