[백준 1012] 유기농 배추 (JAVA)

백준 1012번 문제 - 유기농 배추

1012번: 유기농 배추

---

문제 분석

 

 

• 배추를 해충으로부터 보호해주는 배추흰지렁이를 구매하려고 한다.
• 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 인접한 다른 배추들도 해충으로부터 보호받을 수 있다. 
  •  인접한 배추 : 상하좌우 네 방향에 있는 배추
• 필요한 최소의 배추흰지렁이 마리 수를 출력해라.

---

해결 포인트

 

• BFS 이용 (DFS도 충분히 가능할 듯)
• 메모리를 최소한으로 쓰기 위해 배추가 있는 위치를 boolean 2차원 배열로 구현
  • 배추가 있는 곳은 true로
• 배추 표시를 알려주는 boolean 2차원 배열에서 배추 위치가 DFS로 확인 됬으면 false로 설정
• BFS 함수를 호출하는 횟수를 출력

---

코드

 

import java.awt.*;
import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    public static int M, N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

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

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

            boolean [][] check = new boolean[N][M];
            for (int i = 0; i < K; i++) {
                st = new StringTokenizer(br.readLine());

                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                check[y][x] = true;
            }

            int count = 0;
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if(check[i][j]) {
                        BFS(check, j, i);
                        count++;
                    }
                }
            }

            bw.write(count + "\n");
        }

        bw.flush();
        bw.close();
    }

    public static void BFS(boolean [][] check, int x, int y) {
        int [] dx = {1,-1,0,0};
        int [] dy = {0,0,1,-1};

        Queue<Point> queue = new LinkedList<>();

        queue.add(new Point(x, y));
        check[y][x] = false;

        while(!queue.isEmpty()) {
            Point value = queue.poll();

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

                if(isOverRound(nx, ny) && check[ny][nx]) {
                    queue.add(new Point(nx, ny));
                    check[ny][nx] = false;
                }
            }
        }
    }

    public static boolean isOverRound(int x, int y) {
        return (x >= 0 && y >= 0 && x < M && y < N);
    }
}