[백준] | JAVA, 자바 | 1012번 - 유기농 배추

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

---

문제 요약 :

1. 배추밭의 가로길이 M, 세로길이 N, 배추가 심어져 있는 위치의 개수 K 입력받기

2. K만큼 배추의 위치 입력받기

3. 지렁이는 배추 근처에 서식하며 해충을 잡아먹음으로써 배추를 보호

4. 한 배추의 상화좌우 네 방향에 다른 배추가 위치한 경우 서로 인접해 있음

5. 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어둠

6. 0은 배추가 심어져 있지 않은 땅, 1은 배추가 심어져 있는 땅

7. 배추밭에 필요한 지렁이의 마리 수 구하기

---

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

public class Main {
    static class Coordinate {
        int x;
        int y;
        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    private static int M, N, K;
    private static int[][] map;
    private static boolean[][] visited;
    private static int[][] delta = {{-1,0},{1,0},{0,-1},{0,1}}; // 상, 하, 좌, 우
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        
        for (int tc = 1; tc <= t; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            // 1. 배추밭의 가로길이 M, 세로길이 N, 배추가 심어져 있는 위치의 개수 K 입력받기
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            map = new int[M][N];

            // 2. K만큼 배추의 위치 입력받기
            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[x][y] = 1;
            }

            visited = new boolean[M][N];
            int cnt = 0;

            for (int i = 0; i < M; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][j] == 1 && !visited[i][j]) {
                        needEarthworm(new Coordinate(i, j));
                        cnt++;
                    }
                }
            }
            // 7. 배추밭에 필요한 지렁이의 마리 수 구하기
            System.out.println(cnt);
        }
    }

    private static void needEarthworm(Coordinate temp) {
        Queue<Coordinate> queue = new ArrayDeque<>();
        queue.add(temp);

        while (!queue.isEmpty()) {
            Coordinate cabbage = queue.poll();

            // 4. 한 배추의 상화좌우 네 방향에 다른 배추가 위치한 경우 서로 인접해 있음
            for (int i = 0; i < 4; i++) {
                int nr = cabbage.x + delta[i][0];
                int nc = cabbage.y + delta[i][1];

                // 6. 0은 배추가 심어져 있지 않은 땅, 1은 배추가 심어져 있는 땅
                if (isRange(nr, nc) && !visited[nr][nc] && map[nr][nc] == 1) {
                    visited[nr][nc] = true;
                    queue.add(new Coordinate(nr, nc));
                }
            }
        }
    }

    private static boolean isRange(int nr, int nc) {
        return nr >= 0 && nr < M && nc >= 0 && nc < N;
    }
}