[BOJ] 1012 - 유기농 배추

문제 링크

1012-유기농 배추

문제 설명

입력

• 배추밭 가로 길이
• 배추밭 세로 길이
• 배추 심어져있는 위치 갯수
• 심어져있는 배추들의 x,y좌표

출력

• 필요한 최소 배추흰지렁이 마리 수

문제 풀이

DFS (깊이 우선 탐색) 이용

import java.util.Scanner;

public class Main {

    static int[][] cabbage;
    static boolean[][] visited;
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, -1, 0, 1};

    static int m, n, k, cnt;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();

        for (int test_case = 1; test_case <= t; test_case++) {
             m = sc.nextInt();
             n = sc.nextInt();
             k = sc.nextInt();

            cabbage = new int[m][n];
            visited = new boolean[m][n];
            for (int i = 0; i < k; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                cabbage[x][y] = 1;
            }

            cnt = 0;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (cabbage[i][j] == 1 && !visited[i][j]) {
                        dfs(i, j);
                        cnt++;
                    }
                }
            }
            System.out.println(cnt);

        }
    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && ny >= 0 && nx < m && ny < n ) {
                if (!visited[nx][ny] && cabbage[nx][ny] == 1) {
                    dfs(nx, ny);
                }
            }
        }
    }
}

이건 앞서 정리했던 10026-적록색약 문제와 아주 같은 문제
적록색약에서는 두가지 경우를 생각해 중간에 배열의 값을 바꿔줘야했지만, 이번 문제는 불필요함.
그래프 탐색에서 가장 기본적인 유형이라고 생각함.
반드시 알아두기 ✅