[백준] 1012 유기농 배추 | DFS, BFS, 그래프 | 실버 Ⅱ | JAVA

📌 문제

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

 

⭐ 해결 방법: 그래프 탐색

그래프 탐색을 위한 대표적인 방법 두 가지를 활용할 수 있습니다.

1. 깊이 우선 탐색(DFS)
   • 스택 또는 재귀를 이용해 한 방향으로 탐색을 계속 진행하다가, 막히면 이전 노드로 돌아옵니다.
2. 너비 우선 탐색(BFS)
   • 큐를 이용해 현재 노드와 인접한 모든 노드를 탐색합니다.

이번 문제는 DFS와 BFS 중 어떤 방법을 사용해도 해결이 가능합니다.

 

⭐ 알고리즘 풀이 과정

1. 배추밭 초기화
   입력받은 가로길이(M), 세로길이(N)에 따라 2차원 배열로 배추밭을 구성합니다.
2. 그래프 탐색을 위한 준비
   방문 여부를 확인하기 위한 배열(visited)과 이동 방향을 나타내는 배열(dx, dy)을 설정합니다.
3. 배추흰지렁이 군집 탐색
   배추가 심어진 모든 좌표에 대해 DFS 또는 BFS를 수행합니다.
   • 방문하지 않은 배추를 찾으면 탐색을 시작하며, 이 과정을 통해 하나의 군집을 탐색 완료합니다.
   • 탐색이 완료될 때마다 군집의 수(count)를 1 증가시킵니다.
4. 출력
   각 테스트 케이스에 대해 필요한 지렁이의 수를 출력합니다.

 

✅ 정답 코드

import java.util.*;

public class Main {
    static int[][] farm;
    static boolean[][] visited;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {-1, 1, 0, 0};
    static int M, N, K;

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

        int T = sc.nextInt(); // 테스트 케이스 개수
        while (T-- > 0) {
            M = sc.nextInt(); // 가로 길이
            N = sc.nextInt(); // 세로 길이
            K = sc.nextInt(); // 배추 위치 개수

            farm = new int[N][M];
            visited = new boolean[N][M];

            // 배추밭 입력
            for (int i = 0; i < K; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                farm[y][x] = 1;
            }

            int count = 0; // 필요한 지렁이 수

            // 모든 좌표를 탐색
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (farm[i][j] == 1 && !visited[i][j]) {
                        dfs(i, j); // 또는 bfs(i, j);
                        count++;
                    }
                }
            }

            System.out.println(count);
        }

        sc.close();
    }

    // 깊이 우선 탐색(DFS)
    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 < N && ny < M) {
                if (farm[nx][ny] == 1 && !visited[nx][ny]) {
                    dfs(nx, ny);
                }
            }
        }
    }

    // 너비 우선 탐색(BFS)
    static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int cx = current[0];
            int cy = current[1];

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

                if (nx >= 0 && ny >= 0 && nx < N && ny < M) {
                    if (farm[nx][ny] == 1 && !visited[nx][ny]) {
                        queue.offer(new int[]{nx, ny});
                        visited[nx][ny] = true;
                    }
                }
            }
        }
    }
}

🗒️ 코드 설명

1. 입력 처리
   • M, N, K를 입력받아 배추밭 크기와 배추 위치를 초기화합니다.
   • farm 배열에 배추가 있는 위치를 1로 설정합니다.
2. DFS 또는 BFS를 이용한 탐색
   • 4방향 탐색(dx, dy)을 통해 인접한 배추를 확인하며, 방문한 곳은 visited 배열에 기록합니다.
3. 결과 출력
   • 탐색이 끝날 때마다 군집 수를 증가시켜 결과로 출력합니다.