[BOJ] 백준 1012 유기농 배추

출처:  https://www.acmicpc.net/problem/1012

 Input 

1

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 62
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

 

 Output 

5
1

배추의 위치는 다음과 같다.

0: 배추가 심어져 있지 않은 땅 / 1: 배추가 심어져 있는 땅

해충을 방지하기 위해 지렁이를 배추 근처에 서식 시키려고 합니다.

지렁이는 인접한(상하좌우) 배추를 통해 이동할 수 있기에 인접한 배추들도 보호받을 수 있습니다.

 

최소 몇 마리의 지렁이가 필요한지 구하는 문제로

배추들이 어떻게 인접하였는지 확인하는 문제입니다.

BFS, DFS를 통해 풀 수 있는 문제이지만 재귀함수를 이용해 처리.

---

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int T = Integer.parseInt(sc.nextLine());
        List<Integer> answer = new ArrayList<>();
        
        for(int idx=0; idx<T ; idx++) {
            
            int M = Integer.parseInt(sc.next());
            int N = Integer.parseInt(sc.next());
            int K = Integer.parseInt(sc.next());
            
            int arr[][] = new int[M][N];
            
            
            for(int i=0; i<K; i++) {
                int x = Integer.parseInt(sc.next());
                int y = Integer.parseInt(sc.next());
                arr[x][y] = 1;
            }
            
            int count = 0;
            
            for(int i=0; i<M; i++) {
                for(int j=0; j<N; j++) {
                    
                    // 각각의 좌표에 대해서 배추가 있는지 확인한다. - '1'
                    if (arr[i][j] == 1) { // 배추가 존재한다면 해당 지점을 기점으로 인접한 배추의 좌표의 값들을 '0'으로 바꾼다.
                        count++;
                        earthWorm(i,j,arr);
                        
                    }
                }
            }
            answer.add(count);
        }
        
        for(int idx=0; idx<T; idx++) {
            System.out.println(answer.get(idx));
        }
        
    }
    
    public static void earthWorm(int x, int y, int[][] arr) {
        arr[x][y] = 0;
        
        // 현재 좌표 왼쪽
        if(x-1 >= 0 && arr[x-1][y] == 1) {
            arr[x-1][y] = 0;
            earthWorm(x-1,y,arr);
        }
        
        // 현재 좌표 오른쪽
        if(x+1 < arr.length && arr[x+1][y] == 1) {
            arr[x+1][y] = 0;
            earthWorm(x+1,y,arr);
        }
        
        // 현재 좌표 아래쪽
        if(y-1 >= 0 && arr[x][y-1] == 1) {
            arr[x][y-1] = 0;
            earthWorm(x,y-1,arr);
        }
        
        // 현재 좌표 위쪽
        if(y+1 < arr[x].length && arr[x][y+1] == 1) {
            arr[x][y+1] = 0;
            earthWorm(x,y+1,arr);
        }
    }
}