[알고리즘 문제] 백준1012 - 유기농배추

문제는 배추의 상/하/좌/우로 움직일 수 있는 지렁이가 있을 때, 해충으로부터 배추를 보호하는데 필요한 지렁이의 개수를 구하는 문제이다.

설명은 이렇지만, 사실 배추의 군집의 개수를 구하는 문제이다. 이 문제는 dfs를 사용해서 풀 수 있다.

 

먼저 배열을 모두 검사하다가, 1을 발견하면 그때 부터 탐색을 시작하는데 상/하/좌/우로 1이 있을 떄 까지 탐색하다가 더이상 탐색할 수 없으면 그때 지렁이 수를 하나 증가시키면된다.

 

코드에서 신기한 점은 탐색을할 때, 배열을 벗어나는지는 검사하지 않는다는 점인데 그 이유는 처음에 배열의 크기를 가로/세로의 크기+1 해주었고, 또 탐색을 할 때, 시작을 0,0가 아닌, 1,1로 시작했기 때문에 절대 배열을 벗어나는 경우가 발생하지 않는다.

 

또 4방향 탐색을 쉽게 하기 위해서 dx,dy라는 배열을 사용했는데 0~3인덱스의 각 값은 우,하,좌,상으로 설정하였다.

import java.util.*;

public class Main {
    // 우,하,좌,상
    static int[] dx = { 1, 0, -1, 0 };
    static int[] dy = { 0, 1, 0, -1 };
    static int[][] farm;
    static int earthworm = 0;

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

        for (int i = 0; i < T; i++) {

            int x = sc.nextInt();
            int y = sc.nextInt();
            farm = new int[y + 2][x + 2];
            int count = sc.nextInt(); // 배추의 수

            for (int k = 0; k < count; k++) {

                int width = sc.nextInt();
                int height = sc.nextInt();
                farm[height + 1][width + 1] = 1;

            }
            for (int yy = 0; yy < y; yy++) {
                for (int xx = 0; xx < x; xx++) {
                    if (farm[yy + 1][xx + 1] == 1) {
                        dfs(yy + 1, xx + 1);
                        earthworm++;
                    }

                }
            }
            System.out.println(earthworm);
            earthworm = 0;
        }
    }

    static void dfs(int y, int x) {

        farm[y][x] = 0;

        for (int i = 0; i < 4; i++) {

            int ny = y + dy[i];
            int nx = x + dx[i];

            if (farm[ny][nx] == 1) {
                dfs(ny, nx);
            }
        }

    }
}