1012번: 유기농 배추

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배합니다. 배추를 보호하기 위해 배추흰지렁이를 구입했는데, 이 지렁이는 상하좌우로 인접한 배추로 이동할 수 있습니다. 따라서 배추들이 모여있는 덩어리(군데)마다 최소 1마리의 지렁이가 필요합니다. 배추밭의 크기와 배추가 심어진 위치가 주어질 때, 각 테스트 케이스에 대해 필요한 최소 배추흰지렁이 마리 수를 구하는 문제입니다.

• 입력: 테스트 케이스의 개수 T, 배추밭의 가로길이 M, 세로길이 N, 배추가 심어져 있는 위치의 개수 K. 이어서 K개의 줄에 배추의 위치 X, Y가 주어집니다.
• 출력: 각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수.

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

풀이

이 문제는 2차원 격자에서 상하좌우로 연결된 구성 요소(Connected Component)의 덩어리 개수를 구하는 전형적인 그래프 탐색 문제입니다. 깊이 우선 탐색(DFS)이나 너비 우선 탐색(BFS) 모두 사용 가능하며, 이 코드에서는 DFS를 활용했습니다.

1. 배열 초기화 및 배추 심기: 가로 크기가 M, 세로 크기가 N이므로 2차원 배열은 a[N][M]으로 선언합니다. 입력으로 주어지는 좌표 X는 열(Column), Y는 행(Row)을 의미하므로 a[Y][X] = 1에 배추가 있음을 표시합니다.
2. 모든 칸 탐색 및 지렁이 투입: 배추밭 전체를 2중 for문으로 순회합니다. 배추가 심어져 있고(a[i][j] == 1), 아직 방문하지 않은 칸(!visited[i][j])을 발견하면 새로운 배추 덩어리를 찾은 것입니다. 이때 필요한 지렁이 수(ans)를 1 증가시키고 해당 위치에서 DFS 탐색을 시작합니다.
3. DFS 탐색 (연결된 배추 찾기): dfs(y, x) 함수는 현재 위치에서 상하좌우 4방향을 확인합니다. 밭의 범위를 벗어나지 않으면서 배추가 있고 아직 방문하지 않은 인접한 칸을 찾으면, 재귀적으로 함수를 호출하여 방문 처리(visited = true)를 합니다. 이 과정이 끝나면 해당 덩어리에 속한 모든 배추가 방문 처리됩니다.
4. 테스트 케이스 반복: 이 과정을 주어진 T번의 테스트 케이스만큼 반복합니다. 매 케이스마다 배추밭 배열(a)과 방문 배열(visited), 정답 변수(ans)를 새롭게 초기화하는 것이 중요합니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static int n, m;
    static int[][] a;
    static boolean[][] visited;
    
    // 상하좌우 탐색을 위한 델타 배열
    static int[] dy = {-1, 0, 1, 0};
    static int[] dx = {0, 1, 0, -1};

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int t = Integer.parseInt(br.readLine());
       while (t-- > 0) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          m = Integer.parseInt(st.nextToken()); // 가로
          n = Integer.parseInt(st.nextToken()); // 세로
          int k = Integer.parseInt(st.nextToken()); // 배추 개수
          
          a = new int[n][m];
          while (k-- > 0) {
             st = new StringTokenizer(br.readLine());
             int x = Integer.parseInt(st.nextToken());
             int y = Integer.parseInt(st.nextToken());
             a[y][x] = 1; // 배추 위치 표시
          }

          visited = new boolean[n][m];
          int ans = 0;
          
          // 배추밭 전체 순회
          for (int i = 0; i < n; i++) {
             for (int j = 0; j < m; j++) {
                // 배추가 있고 방문하지 않은 칸이면 새로운 군집 발견
                if (a[i][j] == 1 && !visited[i][j]) {
                   dfs(i, j); // 해당 군집 방문 처리
                   ans++;     // 지렁이 수 증가
                }
             }
          }

          bw.write(ans + "\n");
       }

       bw.flush();
    }

    // DFS를 이용해 인접한 배추들을 방문 처리하는 함수
    static void dfs(int y, int x) {
       visited[y][x] = true;

       // 상하좌우 4방향 탐색
       for (int i = 0; i < 4; i++) {
          int ny = y + dy[i];
          int nx = x + dx[i];
          
          // 배추밭 범위를 벗어나면 무시
          if (ny < 0 || nx < 0 || ny >= n || nx >= m)
             continue;
          // 배추가 없거나 이미 방문한 칸이면 무시
          if (a[ny][nx] == 0 || visited[ny][nx])
             continue;
             
          // 인접한 배추로 탐색 이어나감
          dfs(ny, nx);
       }
    }
}

알고리즘 분류

그래프 탐색 (Graph Traversal), 깊이 우선 탐색 (DFS), 너비 우선 탐색 (BFS)