💡문제 분석 요약

• 입력: 여러 개의 테스트 케이스가 주어진다. 각 테스트 케이스는 배추가 심어진 가로와 세로 크기(즉, M x N 크기), 그리고 배추가 심어진 좌표들의 리스트가 주어진다.
• 목표: 서로 인접한 배추들(상, 하, 좌, 우)을 한 군집으로 간주하여, 몇 개의 배추 군집이 있는지 세는 것이다.
• 그래프 탐색: 인접한 배추들끼리 연결된 부분을 그래프의 노드로 보고, DFS 또는 BFS를 사용해 군집을 찾는다.

💡알고리즘 설계

• 그래프 표현
  • 2차원 배열을 이용해 배추가 심어진 좌표를 표현한다.
  • 배추가 심어진 곳은 1, 배추가 없는 곳은 0으로 표시한다.
• DFS/BFS 탐색
  • 각 배추 좌표에서 상, 하, 좌, 우로 인접한 배추가 있는지 확인하여 방문하지 않은 배추들을 방문 처리한다.
  • 하나의 배추에서 시작해 인접한 배추들을 모두 탐색한 후, 군집을 세기 위해 군집 카운터를 증가시킨다.
• 방문 처리
  • 방문한 배추는 다시 방문하지 않도록 처리한다 (방문 배열을 사용하거나 값을 0으로 변경)
• 탐색 완료 후 군집 수 카운트
  • 모든 좌표에 대해 DFS/BFS를 수행하고, 탐색을 마친 후 군집 수를 출력한다.

💡코드

const fs = require('fs');
const path = require('path');

const input = fs.readFileSync(path.join(__dirname, 'input.txt')).toString().trim().split('\\n');

function solution(input) {
  // 첫 번째 값을 테스트 케이스 수 T로, 나머지는 각각의 케이스로 분리
  const [T, ...cases] = input;

  // 상, 하, 좌, 우 방향을 나타내는 배열
  const directions = [
    [-1, 0], [1, 0], [0, -1], [0, 1] // 위, 아래, 왼쪽, 오른쪽
  ];

  // DFS 함수: 현재 위치 (x, y)에서 시작해 연결된 모든 배추를 방문
  const dfs = (x, y, grid, visited, N, M) => {
    // 현재 위치를 방문 처리
    visited[x][y] = true;

    // 상, 하, 좌, 우로 이동
    for (let [dx, dy] of directions) {
      const nx = x + dx;  // 새로운 x좌표
      const ny = y + dy;  // 새로운 y좌표

      // 유효한 좌표 내에 있고, 배추가 있으며, 아직 방문하지 않았다면 탐색
      if (nx >= 0 && ny >= 0 && nx < N && ny < M && grid[nx][ny] === 1 && !visited[nx][ny]) {
        dfs(nx, ny, grid, visited, N, M); 
      }
    }
  };

  
  let idx = 0;  // 각 테스트 케이스의 시작 인덱스
  let result = [];  // 각 테스트 케이스의 결과를 저장할 배열

  // 테스트 케이스 수만큼 반복
  for (let t = 0; t < T; t++) {
    // 가로 M, 세로 N, 배추의 개수 K 추출
    const [M, N, K] = cases[idx].split(' ').map(Number);

    idx++;

    // 농장을 표현하는 2차원 배열(grid)와 방문 여부를 저장하는 배열(visited) 초기화
    const grid = Array.from({ length: N }, () => Array(M).fill(0));
    const visited = Array.from({ length: N }, () => Array(M).fill(false));

    // 배추 심기
    for (let i = 0; i < K; i++) {
      const [x, y] = cases[idx].split(' ').map(Number);
      grid[y][x] = 1;  // 배추가 심어진 좌표를 1로 표시
      idx++;
    }

    let count = 0;  // 군집의 개수를 세기 위한 변수

    // 모든 좌표를 돌면서 배추가 심어져 있고 방문하지 않은 경우 DFS 탐색
    for (let i = 0; i < N; i++) {
      for (let j = 0; j < M; j++) {
        if (grid[i][j] === 1 && !visited[i][j]) {
          dfs(i, j, grid, visited, N, M);  
          // 배추 군집 탐색
          
          count++;  
          // 하나의 군집을 찾았으므로 카운트 증가
        }
      }
    }

    // 결과 배열에 군집 수 추가
    result.push(count);
  }

  console.log(result.join('\\n'));
}

solution(input);

💡시간복잡도

• 그래프의 각 노드를 한 번씩 방문하고, 각 노드에서 상하좌우의 4방향을 확인하기 때문에시간 복잡도는 O(M × N)이다.
  • M은 가로 길이, N은 세로 길이
• DFS나 BFS 자체는 O(V + E)인데, 이 문제에서 V(노드의 수)는 배추 좌표 수, E(간선의 수)는 인접한 배추의 수에 해당한다.