백준 No.1012 유기농 배추 - JAVA

문제

차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추 흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다.

한나가 배추를  재배하는 땅은 고르지 못해서 배추를 군데군데 심어놓았다. 배추들이 모여잇는 곳에는 배추 흰 지렁이가 한 마리만 있으면 되므로 서로 인접해 있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다 0은 배추가 심어져있지 않은 땅이고, 1은 배추가 심어져있는 땅을 나타낸다.

 

 

입력

2
10 8 17
0 0
1 0
1 1
4 2
4 3
4 5
2 4
3 4
7 4
8 4
9 4
7 5
8 5
9 5
7 6
8 6
9 6
10 10 1
5 5

 

 

해당 문제는 단지번호붙히기와 거의 유사한 문제였다.

이런 문제들은 main에서 bfs메소드를 여러번 호출해야한다. 그래야만 상하좌우를 탐색하여 끊기는지 안 끊기는지 체크할 수 있다.

처음에 0,0 이 들어가면 map[0][0] = 1 이고 첫 방문이므로 바로 통과하면서 bfs에 들어간다.

bfs 메소드는 해당 x,y를 받아서 상하좌우 값이 1(즉, 배추가 심어졌다면) 계속 탐색해나간다. 이 과정에서 모두 방문한 곳은 방문처리를 해버린다. 그러고 나서 상하좌우에 1이 연결된 곳을 다 탐색하고 나면 다시 

해당 for문으로 돌아와 카운트 +1 을 한다. 그러면서 점차 계속 x,y를 탐색하는데 처음 시작했던 bfs 때문에

 해당 1들은 if문에서 걸러진다. 그러고 계속 1을 찾아가다가 

가운데 1을 발견하고 bfs메소드를 다시 실행한다. 이 과정에서 또 위에 과정을 반복하면서 계속 탐색해나간다.

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

public class Main {

    static int count;
    static int dx[] = {1,0,-1,0};
    static int dy[] = {0,1,0,-1};
    static int map[][];

    static int M,N;
    static  boolean visited[][];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int A = Integer.parseInt(br.readLine());
        StringTokenizer st;

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

             M = Integer.parseInt(st.nextToken());   //배추밭 가로
             N = Integer.parseInt(st.nextToken());   //배추밭 세로
            int K = Integer.parseInt(st.nextToken());   //배추 심어진 개수

            map = new int[M][N];
            visited = new boolean[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;
            }
            count = 0;
            for (int j = 0; j < M ; j++) {
                for (int k = 0; k < N; k++) {
                      if(map[j][k] == 1 && !visited[j][k]){
                          bfs(j,k);
                          count++;
                      }
                }
            }

            System.out.println(count);
        }

    }

    private static void bfs(int j,int k) {

        Queue<Node> queue = new LinkedList<>();
        queue.add(new Node(j,k));

        visited[j][k] =true;

        while (!queue.isEmpty()){
            Node now = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nextX = now.x + dx[i];
                int nextY = now.y + dy[i];

                if(nextX >= 0 && nextY >= 0 && nextX < M && nextY < N){
                        if(!visited[nextX][nextY]){
                            if(map[nextX][nextY] == 1){
                                queue.add(new Node(nextX,nextY));
                                visited[nextX][nextY] = true;
                            }
                        }
                }
            }
        }
    }

    static class Node{
        int x;
        int y;
        public Node(int x,int y){
                this.x = x;
                this.y = y;
        }
    }
}