백준 1012번: 유기농 배추

 

 

그래프 탐색 방법

1. 입력을 받아 **배추밭(map)**을 2차원 배열로 생성
2. 방문 여부를 체크할 visited 배열을 선언
3. 배추(1)이고 방문하지 않은 곳을 발견하면 BFS 탐색 시작
4. BFS 탐색을 통해 하나의 그룹을 완전히 방문 처리
5. 탐색이 끝날 때마다 count(흰지렁이 수) 증가

BFS를 사용하면 연결된 모든 배추를 한 번에 방문할 수 있어, 효율적으로 그룹을 찾을 수 있습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

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

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());

        while (N-- > 0) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            map = new int[x][y];
            visited = new boolean[x][y];

            for (int i = 0; i < M; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());

                map[a][b] = 1;
            }

            for (int i = 0; i < x; i++) {
                for (int j = 0; j < y; j++) {
                    if (map[i][j] == 1 && !visited[i][j]) {
                        bfs(i, j);
                        count++;
                    }
                }
            }

            System.out.println(count);
            count = 0;
        }
    }

    static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        visited[x][y] = true;
        queue.offer(new int[] {x, y});

        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int nowX = arr[0];
            int nowY = arr[1];

            for (int i = 0; i < 4; i++) {
                int nextX = nowX + dx[i];
                int nextY = nowY + dy[i];

                if (nextX < 0 || nextY < 0 || nextX >= map.length || nextY >= map[0].length) continue;
                if (visited[nextX][nextY] || map[nextX][nextY] == 0) continue;

                queue.offer(new int[] {nextX, nextY});
                visited[nextX][nextY] = true;
            }
        }
    }
}

 

 

시간 복잡도 분석

• 배추의 개수 K ≤ 2500이므로 최악의 경우 50×50(=2500)개를 모두 탐색해야 합니다.
• BFS의 시간 복잡도는 O(V + E) (V: 정점, E: 간선)인데,
  이 문제에서는 간선의 개수가 최대 4V (최대 4방향 이동 가능)입니다.
• 따라서 최악의 경우 **O(5V) ≈ O(V)**로 볼 수 있습니다.

즉, 최대 2500번의 탐색으로 해결 가능하여 충분히 빠르게 동작합니다.