Q. 1012 자바 : 유기농 배추

Q. 1012 자바 : 유기농 배추

 

문제 : boj.kr/1012

실버 2 난이도의 문제이다.

 

이전 글에서 푼 문제인 단지번호 붙이기와 거의 비슷한 문제이다.

배추를 재배하는 땅들의 좌표가 주어진다.

배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 될 때,

총 몇 마리의 지렁이가 필요한지 계산하는 문제이다.

 

지도의 크기 M, N이 주어지는데,

격자형 그래프 순회 문제의 경우 모든 점을 순회해야 하므로 시간 복잡도는 O(NM)이고,

문제에서N, M의 최대값은 각각 50이므로시간초과는 걱정하지 않아도 된다.

또한 입력을 받을 때 자료형은 0과 1로만 구분되므로 boolean을 사용했다.

 

문제를 푼 방식은

1. 탐색이 가능한 경우(arr[y][x] = true) 방문하고, 이후에 탐색을 진행하며 방문 횟수를 저장한다.

1-1. 방문한 경우 방문한 곳에 대한 표시는 반드시 해야 한다.(arr[y][x] = false)

1-2. 탐색이 가능한 경우 배추흰지렁이의 수를 하나 더해준다(cnt++)

2. 이후 전체 탐색이 끝났을 때 cnt를 출력한다.

 

문제에서 주의해야 할 점으로는 테스트케이스가 여러 개 주어진다고 했으므로,

각각의 케이스를 함수로 나눠서 모두 처리할 수 있게 작성했다.

 

시간복잡도를 계산하면 

0. 테스트 케이스의 수 O(T)

1. 격자형 그래프 순회 - O(NM)

따라서 약 O(NM)의시간복잡도가 나오게 된다. 따라서 위 문제를 푸는데는 지장이 없다.

 

그래프 탐색 문제들의 경우

특수한 경우를 제외하고는 bfs, dfs 두 방식 모두 사용 가능하므로 두 방식을 통해서 풀었다

풀이는 아래와 같다.

import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
    static FastReader scan = new FastReader();
    static StringBuilder sb = new StringBuilder();

    static int test_case, arrY, arrX, N;
    static boolean[][] arr;

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

    static void input() {

        arrX = scan.nextInt();
        arrY = scan.nextInt();

        N = scan.nextInt();
        arr = new boolean[arrY][arrX];

        for (int i = 0; i < N; i++) {
            int x = scan.nextInt();
            int y = scan.nextInt();
            arr[y][x] = true;
        }
    }

    static void dfs(int y, int x) {

        arr[y][x] = false;
        for (int i = 0; i < 4; i++) {
            int nextY = y + dy[i];
            int nextX = x + dx[i];
            if (nextX == -1 || nextX == arrX || nextY == -1 || nextY == arrY) continue;
            if (arr[nextY][nextX]) dfs(nextY, nextX);
        }
    }

    static void bfs(int y, int x) {

        Queue<int[]> que = new LinkedList<>();
        arr[y][x] = false;
        que.add(new int[]{y, x});

        while (!que.isEmpty()) {
            int[] point = que.poll();
            for (int i = 0; i < 4; i++) {
                int nextY = point[0] + dy[i];
                int nextX = point[1] + dx[i];
                if (nextX == -1 || nextX == arrX || nextY == -1 || nextY == arrY) continue;
                if (arr[nextY][nextX]) {
                    que.add(new int[]{nextY, nextX});
                    arr[nextY][nextX] = false;
                }
            }
        }
    }

    static void pro() {

        int cnt = 0;
        for (int i = 0; i < arrY; i++) {
            for (int j = 0; j < arrX; j++) {
                if (arr[i][j]) {
                    cnt++;
                    bfs(i, j);
                    // dfs(i, j);
                }
            }
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) {

        test_case = scan.nextInt();
        for (int tc = 0; tc < test_case; tc++) {
            input();
            pro();
        }
    }


    static class FastReader {
        // BufferedReader의 빠른 속도, 
        // + Scanner의 타입별 입력값을 받는 기능을 혼합
        // (자바 내부에 구현된 Scanner는 속도가 느림)
        // 다른분의 코드를 참고한 코드
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}