백준 1012번 - 유기농 배추(DFS)

 

위 문제와 비슷한 문제

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

 

 

▶코드

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

public class Main{
    static int cabbage[][];
    static boolean visited[][];
    static int dx[] = {0,0,-1,1};
    static int dy[] = {-1,1,0,0};
    static int N, M, K;

    static LinkedList<Integer> result;
    static int cnt;

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

        cnt = 1;

        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());
            result =  new LinkedList<>();
            cabbage = new int[N][M];
            visited = new boolean[N][M];
            for(int j=0;j<K;j++){
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                cabbage[y][x] = 1;
            }
            for(int z=0; z<N;z++){
                for(int j=0;j<M;j++){
                    if(!visited[z][j] && cabbage[z][j]==1){
                        dfs(z,j);
                        result.add(cnt);
                        cnt=1;
                    }
                }
            }
            System.out.println(result.size());
        }

    }
    public static void dfs(int x, int y){
        visited[x][y] = true;
        for(int i=0;i<4;i++){
            int nx = dx[i]+x;
            int ny = dy[i]+y;
            if(nx >= 0 && ny >=0 && nx< N && ny < M && !visited[nx][ny] && cabbage[nx][ny] == 1){
                cnt++;
                dfs(nx, ny);
            }
        }
    }
}