데일리썽

문제 제목 : 유기농 배추

난이도 : 하

문제 유형 : DFS, BFS

추천 풀이 시간 : 30분 (못하면 2배 60분)

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

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static int t, m, n, k;
    public static int[][] ground = new int[50][50];
    public static boolean[][] visited = new boolean[50][50];

    public static int[] moveX = {0, 0, -1, 1};
    public static int[] moveY = {1, -1, 0, 0};

    public static void bfs(int x, int y) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[] {x, y});
        visited[x][y] = true;

        while (!queue.isEmpty()) {
            int[] now = queue.poll();
            int nowX = now[0];
            int nowY = now[1];

            for (int i = 0; i < 4; i++) {
                int nextX = nowX + moveX[i];
                int nextY = nowY + moveY[i];
                if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
                    if (ground[nextX][nextY] == 1 && !visited[nextX][nextY]) {
                        queue.offer(new int[] {nextX, nextY});
                        visited[nextX][nextY] = true;
                    }
                }
            }
        }
    }

    public static void dfs(int x, int y) {
        visited[x][y] = true;

        for (int i = 0; i < 4; i++) {
            int nextX = x + moveX[i];
            int nextY = y + moveY[i];

            if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < m) {
                if (ground[nextX][nextY] == 1 && !visited[nextX][nextY]) {
                    dfs(nextX, nextY);
                }
            }
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        t = sc.nextInt();

        for (int i = 0; i < t; i++) {
            m = sc.nextInt();
            n = sc.nextInt();
            k = sc.nextInt();

            ground = new int[50][50];
            visited = new boolean[50][50];

            for (int j = 0; j < k; j++) {
                int y = sc.nextInt();
                int x = sc.nextInt();
                ground[x][y] = 1;
            }

            int result = 0;

            for (int j = 0; j < n; j++) {
                for (int k = 0; k < m; k++) {
                    if (ground[j][k] == 1 && !visited[j][k]) {
                      //  bfs(j, k);
                        dfs(j, k);
                        result++;
                    }
                }
            }

            System.out.println(result);
        }
    }
}