[백준]1012: 유기농 배추 (DFS 풀이)

DFS 연습문제로 제격이다. 비교적 쉬운 문제인 것 같다.

---

정답 코드

package graph;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Q1012 {
    static int M, N, cnt;
    static int[] row = {0, 0, 1, -1};
    static int[] col = {1, -1, 0, 0};

    public static boolean isSafe(int[][] arr, int x, int y) {
        if (x < N && y < M) {
            if ((x >= 0 && y >= 0) && arr[x][y] == 1) {
                return true;
            }
        }
        return false;
    }

    public static void find(int[][] arr, int x, int y) {
            arr[x][y] = 0;
            for (int l = 0; l < 4; l++) {
                int newX = x + row[l];
                int newY = y + col[l];
                if (isSafe(arr, newX, newY)) {
                    find(arr, newX, newY);
                }
            }
    }

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

        for (int i = 0; i < T; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            cnt = 0;

            int[][] lett = new int[N][M];
            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine());
                int y = Integer.parseInt(st.nextToken());
                int x = Integer.parseInt(st.nextToken());
                lett[x][y] = 1;
            }

            for (int j = 0; j < N; j++) {
                for (int k = 0; k < M; k++) {
                    if (lett[j][k] == 1) {
                        cnt++;
                        find(lett, j, k);
                    }
                }
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb);
    }
}

---

 

우선 메인에서 돌아가는 코드를 살펴보면,

for (int j = 0; j < N; j++) {
    for (int k = 0; k < M; k++) {
        if (lett[j][k] == 1) {
            cnt++;
            find(lett, j, k);
        }
    }
}
sb.append(cnt).append("\n");

 

이 부분이 있는데, 요약을 해보자면, 양배추가 존재하는 위치를 찾으면, 카운트를 더해줍니다.

이후, find 함수로 그 위치와 인접해 있는 배추들을 다 갉아먹게 해서 그 그룹의 배추들을 싹 다 지워주는것입니다!!

그렇게 해서 결국 카운트는 그룹을 만났을때만 더해지게 되는~그런 코드입니당.

---

static int[] row = {0, 0, 1, -1};
static int[] col = {1, -1, 0, 0};

public static boolean isSafe(int[][] arr, int x, int y) {
    if (x < N && y < M) {
        if ((x >= 0 && y >= 0) && arr[x][y] == 1) {
            return true;
        }
    }
    return false;
}

public static void find(int[][] arr, int x, int y) {
        arr[x][y] = 0;
        for (int l = 0; l < 4; l++) {
            int newX = x + row[l];
            int newY = y + col[l];
            if (isSafe(arr, newX, newY)) {
                find(arr, newX, newY);
            }
        }
}

row와 col에 더해줄 방향값을 동서남북으로 선언해주었습니당.

->

isSafe 함수로 안전한 범위에 있는지, 배추가 존재하는 위치인지 검사를 해줍니다.

->

find 함수에서는 방문한 위치를 0으로 바꿔서 다시 돌아가는 경우를 방지합니다

->

for문으로 방향값을 더해가면서 isSafe함수를 적용시킵니다.

->

만약 안전한 위치라면(배추가 존재), find를 재귀시켜줍니다.

 

원래라면 visited배열을 따로 만들어서 검사를 해주는것이 맞지만, 그냥 배추밭을 전부 다 0으로 만들기 위한 코드이기 때문에 따로 선언하지는 않았습니다.