[Java] BOJ 1012 유기농 배추

문제 

문제 링크 https://www.acmicpc.net/problem/1012

• 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다.
• 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다.
• 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다.
• 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다.
• 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.
• 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다.
• 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다.
• 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다.
• 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

  1	1	0	0	0	0	0	0	0	0
  0	1	0	0	0	0	0	0	0	0
  0	0	0	0	1	0	0	0	0	0
  0	0	0	0	1	0	0	0	0	0
  0	0	1	1	0	0	0	1	1	1
  0	0	0	0	1	0	0	1	1	1

• 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다.
• 그 다음 줄부터 각각의 테스트 케이스에 대해 첫째 줄에는 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1 ≤ N ≤ 50), 그리고 배추가 심어져 있는 위치의 개수 K(1 ≤ K ≤ 2500)이 주어진다.
• 그 다음 K줄에는 배추의 위치 X(0 ≤ X ≤ M-1), Y(0 ≤ Y ≤ N-1)가 주어진다.
• 두 배추의 위치가 같은 경우는 없다.
• 각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력한다.

아이디어

• boolean 배열을 M과 N크기로 생성한다.
• 입력을 받은 좌표를 true로 바꾼다.
• 그리고 이중 for문을 돌면서 해당 좌표가 true일 경우, BFS를 돌린다.
• BFS를 돌릴때, Point를 써서 x값과 y값을 Queue에 저장한다.
• 그리고 while문을 돌리는데 Queue가 빌때까지 반복한다.
• 그리고 새로운 변수들에 .peek().x와 .peek().y를 사용하여 Queue에 넣었던 x와 y값을 저장한다.
• 그리고 for문을 4번 반복하면서 위에 선언해주었던 상하좌우 좌표를 기존 좌표값에 더한 값을 계속 새로운 변수에 선언해준다.
• 새로운 변수에 저장된 좌표가 기존 배열의 범위를 넘어가면 continue하고, 범위안이라면 배열값이 true인지 확인한 뒤, 이동한 좌표값을 false로 바꿔주고 해당 좌표를 Queue에 넣어준다.
• 그리고 BFS가 돌때마다 배추흰지렁이가 한마리씩 더 필요하다는 뜻이므로 BFS돌때마다 카운트를 + 1한다. 

겪은 시행착오

• X

오랜만의 BFS.... 기억을 더듬어가며 열심히 풀었다... 힘들다 ㅜㅜ 앞으로 나에게 닥칠 그래프 시련들이 두렵다 ㅜㅜ

코드

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

public class BOJ1012 {

    static boolean field[][];
    static int dx[] = {-1, 1, 0, 0};
    static int dy[] = {0, 0, -1, 1};

    static int M;

    static int N;

    static int cnt;

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

        // 테스트케이스 개수
        int T = Integer.parseInt(br.readLine());

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

            // 배추밭 가로 길이
            M = Integer.parseInt(st.nextToken());

            // 배추밭 세로 길이
            N = Integer.parseInt(st.nextToken());

            // 배추가 심어져 있는 위치의 개수
            int K = Integer.parseInt(st.nextToken());

            field = new boolean[N][M];

            // 지렁이 개수 카운트할 변수
            cnt = 0;

            for(int i = 0; i < K; i++){
                StringTokenizer st2 = new StringTokenizer(br.readLine());

                int m = Integer.parseInt(st2.nextToken());
                int n = Integer.parseInt(st2.nextToken());

                // 입력받은 위치 값을 true로 변환 (배추가 있으므로)
                field[n][m] = true;
            }

            // 좌표값을 돌려가며 해당 좌표에 배추가 있으면
            // BFS를 돌림
            for(int i = 0; i < N; i++){
                for(int j = 0; j < M; j++){
                    if(field[i][j]){
                        BFS(i, j);

                        // BFS를 돌린 횟수가 지렁이 개수이므로 카운트 + 1
                        cnt = cnt + 1;
                    }
                }
            }

            sb.append(cnt + "\n");
        }

        System.out.println(sb);
    }

    static public void BFS(int i, int j){
        Queue<Point> q = new LinkedList<>();

        // Queue 값에 x,y값을 넣어줌
        q.offer(new Point(i, j));

        while(!q.isEmpty()){
            // x, y값을 변수에 저장
            int nx = q.peek().x;
            int ny = q.peek().y;

            q.poll();

            for(int d = 0; d < 4; d++){
                int mx = nx + dx[d];
                int my = ny + dy[d];

                // 만약 배열의 범위를 넘어설 경우, continue
                if(mx >= N || mx < 0 || my >= M || my < 0){
                    continue;
                }

                // 만약 이동한 지역에 배추가 있다면
                if(field[mx][my]){
                    // 그 지역 값을 false로 바꿔주고
                    field[mx][my] = false;

                    // 그 좌표값을 Queue에 넣어줌
                    q.offer(new Point(mx, my));
                }
            }
        }
    }
}