문제

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

---

풀이

밭의 크기, 배추의 개수와 위치를 이용해 배추흰지렁이의 필요한 최소 마릿수를 구하는 문제
$\to$ 인접한 배추의 집합 개수를 반환하는 문제

1. 밭을 순회하며 배추가 심어져 있는지 확인
2. 심어져 있다면 마릿수를 증가 시키고 인접한 배추가 존재하지 않을 때 까지 탐색
3. DFS or BFS 활용, 방문 처리

---

소스 코드

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

public class Main {
    static int[] dx = { 0, 1, 0, -1 };
    static int[] dy = { 1, 0, -1, 0 };
    static int[][] map;
    static boolean[][] visit;

    static int cx, cy;
    static int M, N, K;
    static int count;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int T = Integer.parseInt(br.readLine());
        for(int i=0; i<T; i++){
            st = new StringTokenizer(br.readLine());

            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            map = new int[N][M];
            visit = new boolean[N][M];

            for(int j=0; j<K; j++){
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[y][x] = 1;
            }

            count = 0;

            for(int j=0; j<N; j++){
                for(int k=0; k<M; k++){
                    if(map[j][k] == 1 && !visit[j][k]){
                        count++;
                        dfs(k, j);
                        //bfs(k, j);
                    }
                }
            }
            sb.append(count).append('\n');
        }
        System.out.print(sb);
    }

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

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

            if(inRange()){
                if(!visit[cy][cx] && map[cy][cx] == 1) {
                    dfs(cx, cy);
                }
            }
        }
    }

    static void bfs(int x, int y){
        visit[y][x] = true;

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[] {x, y});

        while (!q.isEmpty()){
            x = q.peek()[0];
            y = q.poll()[1];

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

                if(inRange()){
                    if(!visit[cy][cx] && map[cy][cx] == 1){
                        q.offer(new int[] {cx, cy});
                        visit[cy][cx] = true;
                    }
                }
            }

        }

    }

    static boolean inRange() {
        return (cy < N && cy >= 0 && cx < M && cx >= 0);
    }
}