[백준 #1012] 유기농 배추

Yujjin·2025년 1월 25일

DFS 백준 코테

백준

목록 보기

3/20

백준 #1012 유기농 배추

백준 #1012

문제 설명👩‍🏫

DFS를 사용하는 그림문제와 동일한 문제다.

입출력 예

입력
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

출력
5
1

내 코드💻

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

public class Main {
    static int h, w;
    static int[][] list;
    static int[][] visited;
    static int []dirX = {0,0,1,-1};
    static int []dirY = {1,-1,0,0};
    static int nowX, nowY;

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

        for(int r = 0;r<re;r++) {
            str = br.readLine();
            StringTokenizer st = new StringTokenizer(str, " ");
            h = Integer.parseInt(st.nextToken());
            w = Integer.parseInt(st.nextToken());
            int bug = Integer.parseInt(st.nextToken());

            list = new int[h][w];
            visited = new int[h][w];

            int count = 0;

            for (int i = 0; i < bug; i++) {
                str = br.readLine();
                st = new StringTokenizer(str, " ");
                int bugX = Integer.parseInt(st.nextToken());
                int bugY = Integer.parseInt(st.nextToken());
                list[bugX][bugY] = 1;
            }


            for (int i = 0; i < h; i++) {
                for (int j = 0; j < w; j++) {
                    if (visited[i][j] == 0 && list[i][j] == 1) {
                        count++;
                        dfs(i, j);
                    }
                }
            }
            System.out.println(count);
        }

    }
    static void dfs(int i,int j){
        visited[i][j] = 1;

        for(int n=0;n<4;n++){
            nowX = i + dirX[n];
            nowY = j + dirY[n];

            if(checking(nowX,nowY) && visited[nowX][nowY]==0 && list[i][j]==1){
                dfs(nowX,nowY);
            }

        }
    }
    static boolean checking(int i,int j){
        return (i>=0 && i<h && j>=0 && j<w);
    }
}