[백준 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

생각 정리

이 역시 그래프 탐색을 통해 푸는 문제이다. (BFS로 풀어보았다.)
나는 이 문제를 '인접해있는 배추들이 몇 군데 퍼져있는지 조사하는 문제'로 재정의 해보았다. (1이 배추가 심어져있는 땅)

그렇다면 해당 위치에서 상하좌우를 탐색하면서 다음을 실행한다.
1. 해당 위치를 방문표시하고 queue에 넣는다.
====다음을 queue가 빌때까지 반복한다====
2. queue의 첫번째 요소를 꺼낸다.
2-1. 방문하지 않았고 배추가 심겨져 있는 곳이라면 (위 문제에서는 1이라면) 방문표시하고 queue에 넣는다.

정리된 생각에 대한 논리

나는 처음에 탐색을 (0, 0)일 때 한번만 실행했다.

이렇게 실행하면,
배추가 심겨져 있는 모든 곳을 탐색해야하는데 (0, 0)에서 상하좌우를 확인하고 주변에 배추가 없으면 (1이 없으면) queue에 아무것도 안들어가니까 거기서 탐색이 멈추게 되었다. (1이 있다고 하더라도 멀리 떨어져있는 1은 탐색하지 못했다.)

=> 그래서 생각한 것은 이중 for문을 (가로, 세로 길이) 돌리면서 모든 위치에서 bfs 함수를 실행하였다.
하지만 이 때, 해당 위치를 방문하지 않았고 배추가 심겨져있는 곳일 때 bfs함수를 실행하였다.

완성

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

class Position{
    int x;
    int y;
    
    Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class BOJ1012 {

    static int M, N, K;
    static int[][] map;
    static boolean[][] visited;
	static int dx[] = {-1, 1, 0, 0};
	static int dy[] = {0, 0, -1, 1};
    static Queue<Position> queue = new LinkedList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
    
        int T = Integer.parseInt(st.nextToken()); //테스트케이스 개수
        
        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];
            visited = new boolean[M][N];

            
            //K번 반복하면서 
            //해당 좌표는 1로 초기화하기 아니면 0,,
            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 cnt = 0;

            for(int j=0; j<M; j++) {
                for(int k=0; k<N; k++) {

                    if(visited[j][k] == false && map[j][k] == 1){

                        visited[j][k] = true;
                        queue.add(new Position(j,k));

                        bfs(j, k);
                        cnt++;
                    }
                }
            }

             System.out.println(cnt);
        }

    }


    static void bfs(int x, int y) {

        if(queue.isEmpty())
            return;

        while(!queue.isEmpty()) {
            Position output = queue.poll();

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

                if(nextX <0 || nextY <0 || nextX >= M || nextY >= N) continue;
                else if(visited[nextX][nextY] == true || map[nextX][nextY] == 0) continue;
                else{
                    visited[nextX][nextY] = true;
                    queue.add(new Position(nextX, nextY));
                }
            }
        }

        
    }
}