[Algorithm] 백준_1012 유기농 배추

문제

가로 M 세로 N의 배추밭에서 K개의 배추를 심습니다. 배추흰지렁이가 배추 근처에서 해충을 잡아먹는데, 상하좌우의 인접한 배추로 이동할 수 있어서 인접한 배추에 1마리만 놓아도 된다.
여기서 최소 필요한 배추흰지렁이 수를 구하면 되는 문제.

풀이

1. T, M, N, K (테스트 케이스, 가로, 세로, 배추 수) 입력받는다.
2. 지도를 돌면서 값이 1인 (배추가 있는) 좌표에서 BFS를 실행한다. (여기서 count를 1씩 증가시킨다)
3. 지도를 벗어나지 않는 범위에서 상하좌우를 이동하면서 배추가 있으면 queue에 넣고, 해당 지도를 0으로 만들어서 다시 재방문하지 않도록 했다.

소스 코드

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

public class Main {
    static int[][] map;
    static int N, M, K;
    static int[] dx = {-1, 1, 0, 0}; //위, 아래, 왼, 오
    static int[] dy = {0, 0, -1, 1};

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

        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[M][N];

            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[x][y] = 1;
            }

            int count = 0;
            for (int x = 0; x < M; x++) {
                for (int y = 0; y < N; y++) {
                    if (map[x][y] ==1 ) {
                        bfs(x, y);
                        count++;
                    }
                }
            }
            bw.write(count + "\n");
        }
        bw.flush();
        br.close();
    }

    private static void bfs (int i, int j) {
        Queue<String> q = new LinkedList<>();
        q.add(i +","+j);
        map[i][j] = 0;

        while (!q.isEmpty()) {
            String[] loc = q.poll().split(",");

            for(int z=0; z<4; z++) {
                int x = Integer.parseInt(loc[0]) + dx[z];
                int y = Integer.parseInt(loc[1]) + dy[z];
                if(x>=0 && x<M && y>=0 && y<N && map[x][y] == 1) {
                    q.add(x+","+y);
                    map[x][y] = 0;
                }
            }
        }
    }
}