[백준] 1021번 유기농 배추

   해당 문제의 원문은 여기서 확인하자.

문제 이해

   배추를 해충으로부터 보호하는 지렁이가 있으며, 이 지렁이는 인접(상하좌우 4방향)한 배추들로 이동하며 인접한 모든 배추들을 보호할 수 있다.

   배추밭에 0을 배추가 심어져 있지 않은 땅, 1을 배추가 심어져 있는 땅이라고 했을 때, 필요한 최소 지렁이의 수를 구하는 문제이다.

   첫째 줄에는 테스트 케이스의 개수 T, 둘때 줄에는 배추밭의 가로 길이 M, 배추밭의 세로길이 N, 배추의 위치 개수 K가 순서대로 입력된다. 그 다음 줄부터는 K줄의 배추의 위치 좌표가 입력된다. 제한 사항은 다음과 같다.

 

• 1 ≤ M, N ≤ 50
• 1 ≤ K ≤ 2500
• 0 ≤ X ≤ M - 1
• 0 ≤ Y ≤ N - 1
• 두 배추의 위치가 같은 경우는 없다.
• 정답은 테스트 케이스의 수만큼 한 줄에 하나씩 출력한다.

 

 

---

접근 방식

   DFS의 개념을 이용해 해결할 수 있는 문제이다. 최소 지렁이 수를 구하기위해 배추밭에 존재하는 배추집합을 차례대로 탐색하고 탐색한 집합을 제거하는 방식으로 진행하였다.

 

 

<방식 1 - 2차원 배열을 순서대로 탐색>

    화살표 방향으로 진행하다 배추가 심어진 1 위치에서 인접한 1을 탐색한다.

 

 

   4방향 탐색 과정에서 배열의 범위를 벗어나는 경우를 주의하며 탐색을 진행한다.

 

 

   탐색이 완료된 1의 경우 중복 탐색을 방지하기위해 0으로 값을 초기화한다.

 

 

   한 집합에 대해 탐색이 끝난 경우 count를 증가시키고 이전 과정을 반복하여 최종 count 값을 구한다.

 

<방식 2 - 좌표를 저장하는 방식>

   DFS 방식에 대해선 차이는 없으며 단지 집합을 찾는 방식만 다르다. 방식 1이 배열을 순서대로 전부 확인한 경우라면 방식 2의 경우는 배추의 좌표를 저장하고 해당 좌표만을 탐색하는 것이다.

 

방식2의 탐색 좌표

 

※ 배추의 좌표만을 확인하는 방법이라 더 빠르다고 생각할 수 있지만 좌표를 저장하는 방법에 따라 속도가 달라질 수 있음을 유의하자.

---

코드

<좌표를 Node 클래스로 저장하는 방식>

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class 백준1021번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer token;
    static int M, N;
    //4방향 탐색을 위한 정의
    static final int[] X = {-1, 1, 0, 0};
    static final int[] Y = {0, 0, -1, 1};

    //좌표값 저장을 위한 노드 클래스
    static class Node {
        int x;
        int y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) throws IOException {
        int testCase = Integer.parseInt(br.readLine());
        int k, x, y, count;
        Queue<Node> q = new LinkedList<>();

        while (testCase-- != 0) {
            token = new StringTokenizer(br.readLine());
            M = Integer.parseInt(token.nextToken());
            N = Integer.parseInt(token.nextToken());
            k = Integer.parseInt(token.nextToken());
            boolean[][] field = new boolean[N][M];
            count = 0;

            while (k-- != 0) {
                token = new StringTokenizer(br.readLine());
                x = Integer.parseInt(token.nextToken());
                y = Integer.parseInt(token.nextToken());
                //배추가 심어진 곳을 true로 초기화
                field[y][x] = true;
                //배축 심어진 좌표를 저장
                q.add(new Node(x, y));
            }

            while (!q.isEmpty()) {
                Node cur = q.poll();
                //배추의 좌표를 하나씩 뽑아 이미 탐색한 경우 다음 좌표로 진행
                if (!field[cur.y][cur.x]) continue;
                //아직 탐색하지 않은 경우 해당 배추를 기준으로 DFS 탐색 진행
                DFS(field, cur.x, cur.y);
                //해당 배추와 인접한 모든 배추 탐색이 끝난 후
                //해당 영역을 담당할 지렁이 수 증가
                count++;
            }

            //현재 테스트 케이스의 최소 지렁이 수를 버퍼에 저장
            bw.append(count + "\n");
        }

        //버퍼 출력
        bw.flush();
    }

    private static void DFS(boolean[][] field, int x, int y) {
        //좌표가 범위를 벗어난 경우
        if (x < 0 || x >= M || y < 0 || y >= N) return;
        //해당 좌표가 이미 탐색된 경우
        else if (!field[y][x]) return ;
        //해당 좌표 탐색이 완료되었으므로 false로 초기화
        field[y][x] = false;
        //4방향에 대해서 탐색 진행
        for (int i = 0; i < 4; i++)
            DFS(field, x + X[i], y + Y[i]);
    }
}

 

<2차원 배열을 전체를 탐색하는 방식>

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

public class 백준1021번 {
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static StringTokenizer token;
    static int M, N;
    //4방향 탐색을 위한 정의
    static final int[] X = {-1, 1, 0, 0};
    static final int[] Y = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        int testCase = Integer.parseInt(br.readLine());
        int k, x, y, count;

        while (testCase-- != 0) {
            token = new StringTokenizer(br.readLine());
            M = Integer.parseInt(token.nextToken());
            N = Integer.parseInt(token.nextToken());
            k = Integer.parseInt(token.nextToken());
            boolean[][] field = new boolean[N][M];
            count = 0;

            while (k-- != 0) {
                token = new StringTokenizer(br.readLine());
                x = Integer.parseInt(token.nextToken());
                y = Integer.parseInt(token.nextToken());
                //배추가 심어진 곳을 true로 초기화
                field[y][x] = true;
            }

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    if (field[i][j]) {
                        DFS(field, j, i);
                        count++;
                    }
                }
            }

            //현재 테스트 케이스의 최소 지렁이 수를 버퍼에 저장
            bw.append(count + "\n");
        }

        //버퍼 출력
        bw.flush();
    }

    private static void DFS(boolean[][] field, int x, int y) {
        //좌표가 범위를 벗어난 경우
        if (x < 0 || x >= M || y < 0 || y >= N) return;
        //해당 좌표가 이미 탐색된 경우
        else if (!field[y][x]) return ;
        //해당 좌표 탐색이 완료되었으므로 false로 초기화
        field[y][x] = false;
        //4방향에 대해서 탐색 진행
        for (int i = 0; i < 4; i++)
            DFS(field, x + X[i], y + Y[i]);
    }
}