[백준] 유기농 배추

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

문제 해석

• 상하좌우로 배추가 위치하면 서로 인접해 있다
• 인접한 배추끼리는 하나의 지렁이면 된다
• 전체 배추위치가 주어질때 필요한 지렁이 수는?

문제 풀이

땅? 맵?을 돌아다니면서 배추가 있는경우 해당 배추에 인접한 모든 배추를 체크해둔다

그리고 다시 체크되지 않은 배추를 찾으며 순회

인접한 배추를 찾는 방법은 dfs 완전 탐색

package com.company;

import java.util.*;

public class Main {

    static int Map[][];
    static boolean[][] Visited;
    static int T, X, Y, N;
    static int count;
    public static void dfs(int x, int y)
    {
        Visited[x][y] = true;

        int dx[] = { 0, 0, 1, -1 };
        int dy[] = { 1, -1, 0, 0 };

        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && ny >= 0 && nx < X && ny < Y) {
                if (!Visited[nx][ny] && Map[nx][ny] == 1) {
                    dfs(nx, ny);
                }
            }
        }
    }

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

        for(int i = 0; i < T; i++) {
            count = 0;
            X = sc.nextInt();
            Y = sc.nextInt();
            N = sc.nextInt();

            Map = new int[X + 1][Y + 1];
            Visited = new boolean[X + 1][Y + 1];

            for (int[] row : Map) {
                Arrays.fill(row, 0);
            }
            for (boolean[] row : Visited) {
                Arrays.fill(row, false);
            }

            for (int j = 0; j < N; j++) {
                int a = sc.nextInt();
                int b = sc.nextInt();
                Map[a][b] = 1;
            }

            for(int j = 0; j < X; j++){
                for(int k = 0; k < Y; k++) {
                    if(Visited[j][k] != true && Map[j][k] == 1){
                        dfs(j, k);
                        count++;
                    }
                }
            }

            System.out.println(count);
        }

    }

}