[백준] 유기농 배추 (2)

이전 글(https://begintoend.tistory.com/49)에서 이어진다.

 

문제를 다시 생각해봤을 때 Queue가 우선순위 큐라는 것을 염두해 두고, 큐가 빌 때 까지 while문을 도는 걸 생략하고 작성한거 같다. 재귀로 구현하기 위해 함수를 따로 빼서 구현하였다. 

package baekjoon;

import java.util.PriorityQueue;
import java.util.Scanner;

class Cabbage {
    int x;
    int y;

    public Cabbage(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int getX() {
        return x;
    }
    public int getY() {
        return y;
    }

}

public class OrganicCabbage_1012 {
    public static int dx[] = {1,0,-1,0};
    public static int dy[] = {0,-1,0,1};

    public static int findCabbage(int graph[][]) {
        int ans = 0;
        PriorityQueue<Cabbage> q = new PriorityQueue<>();

        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph[i].length; j++) {
                // 만약 배추가 심겨져 있다면
                if(graph[i][j]==1) {
                    Cabbage cab = new Cabbage(i,j);
                    cabbage(cab, graph, q);
                    ans += 1;
                }
            }
        }

        return ans;
    }

    public static void cabbage(Cabbage cab, int graph[][], PriorityQueue<Cabbage> q) {
        while(!q.isEmpty()) {
            q.add(cab);
            // 상하좌우를 살핌
            for (int k = 0; k < 4; k++) {
                int nx = cab.getX() + dx[k];
                int ny = cab.getY() + dy[k];
                // 벗어난 공간이라면 건너뜀.
                if (nx < 0 || ny < 0 || nx > graph.length - 1 || ny > graph[0].length - 1) {
                    continue;
                }
                // 배추가 새로 심겨진 곳을 발견한다면?
                if (graph[nx][ny] == 1 && q.poll().getX() != nx && q.poll().getY() != ny) {
                    q.add(new Cabbage(nx, ny));
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int graph[][];
        for (int i = 0; i < T; i++) {
            int M = sc.nextInt();
            int N = sc.nextInt();
            int K = sc.nextInt();
            graph = new int[M][N];

            for (int j = 0; j < K; j++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                graph[x][y] = sc.nextInt();
            }

            findCabbage(graph);

        }


    }
}

그런데 생각을 다시 해보니 ans를 1이 나올 때마다 더하면 1이 나오는 경우의 수를 더하는 것이기에 적절하지 않고, 1인 경우 곧 배추가 있는 경우 큐에 add 하고 배추 벌레의 수인 ans를 1하기 전에, 이전으로부터 큐에 삽입한 수가 있는지 체크를 한 후 ans 값에 1을 더하는 식으로 생각을 해봤다. 

package baekjoon;

import java.util.PriorityQueue;
import java.util.Scanner;

class Cabbage {
    int x;
    int y;

    public Cabbage(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int getX() {
        return x;
    }
    public int getY() {
        return y;
    }

}

public class OrganicCabbage_1012 {
    public static void findCabbage(Cabbage cab, int graph[][]) {

        int dx[] = {0,1,0,-1};
        int dy[] = {-1,0,1,0};
        PriorityQueue<Cabbage> q = new PriorityQueue<>();

        while(!q.isEmpty()) {
            for (int i = 0; i < 4; i++) {
                int nx = cab.getX() + dx[i];
                int ny = cab.getY() + dy[i];
                if(nx<0 || ny<0 || nx > graph.length-1 || ny > graph[0].length-1) {
                    continue;
                }

                if(graph[nx][ny]==1) {
                    q.add(new Cabbage(nx, ny));
                }

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

        // 테스트 케이스
        for (int i = 0; i < T; i++) {
            // M*N 공간
            int M = sc.nextInt();
            int N = sc.nextInt();
            // 배추의 갯수
            int K = sc.nextInt();
            graph = new int[M][N];
            // 배추가 있는 좌표
            for (int j = 0; j < K; j++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                graph[x][y] = 1;
            }
            // 답을 담을 변수
            int ans = 0;
            
            // 그래프 탐색
            for (int j = 0; j < M; j++) {
                for (int k = 0; k < N; k++) {
                    // 배추가 심어져 있는 부분 확인
                    if(graph[j][k]==1) {
                        Cabbage cab = new Cabbage(j,k);
                        findCabbage(cab, graph);
                    }
                }
            }

        }
    }
}

 일단 이렇게 생각하고 우선순위 큐는 정렬된 채로 들어가고 있으니 탐색을 하면서 만약 근방에 배추가 있고, 큐에 들어가 있다면 카운트를 하지 않고, 큐에 들어가 있다면 카운트 하는 방식으로 생각하면 될 거 같다. 

 

그렇다면 q를 findCabbage 안에 선언하면 계속 초기화가 된 빈 큐가 될테니 배추가 있는 부분을 저장하기 위해서는 그래프 탐색 때에 넣는 것으로 다시 고쳐야 할 거 같다.