[알고리즘][DFS][1012] 유기농배추

[알고리즘][DFS][1012] 유기농배추

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

[풀이]

• 배추밭을 배열로 만든 뒤 배추의 위치를 1로 만들어준다.
• [TIP]  Arrays.fill(array이름, 넣을 value) 를 이용하면 쉽게 초기화 할 수 있다.
• 1의 값을 갖고있는 필드를 찾고 count 값을 올려준다. 
• 그 다음, 필드 주변을 상하좌우 DFS(재귀)로 탐색해준다. 

[코드]

package algorithm_DFS;
 
 
import java.util.Arrays;
import java.util.Scanner;
 
public class q_1012 {
    static int m;
    static int n;
    public static int[][] field;
    public static int[][] move = new int[][] {{-1,0},{0,-1},{1,0},{0,1}};
 
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int tc_num = scan.nextInt();
        int k;
        for(int tc=1;tc<=tc_num;tc++) {
            n = scan.nextInt();
            m = scan.nextInt();
            k = scan.nextInt();
            field = new int[n][m];
            for(int i=0;i<n;i++) {
                Arrays.fill(field[i], 0);
            }
            for(int i=0;i<k;i++) {
                int x = scan.nextInt();
                int y = scan.nextInt();
                field[x][y] = 1;
            }
            
            int count = 0;
            for(int i=0;i<n;i++) {
                for(int j=0;j<m;j++) {
                    if(field[i][j]==1) {
                        count++;
                        dfs(i, j);
                    }
                }
            }
            System.out.println(count);
            
        }
    }
    
    //재귀를 이용하여 풀도록 한다.
    public static void dfs(int x, int y) {
        field[x][y]=0;
        for(int i=0;i<4;i++) {
            int move_x = x + move[i][0];
            int move_y = y + move[i][1];
            if(move_x < 0 || move_x >= n || move_y < 0 || move_y >= m)
                continue;
            if(field[move_x][move_y] != 1) 
                continue;
            dfs(move_x,move_y);
        }
    }    
}