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

문제 링크 : https://www.acmicpc.net/problem/1012

1012번: 유기농 배추

처음에는 M*N 만큼 for문을 돌아서 상하좌우 인덱스로 1을 찾은 후에 카운트 하는 단순한 문제로 생각했었는데, 예상 외로 여러가지 따질 문제 였던 거 같다. 

 

처음에 짰던 코드를 써보자면 다음과 같다.

package baekjoon;

import java.util.Scanner;

public class OrganicCabbage_1012 {
    public static int findCabbage(int graph[][]) {
        int ans = 0;
        int dx[] = {1,0,-1,0};
        int dy[] = {0,-1,0,1};

        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph[i].length; j++) {

            }
        }

        return ans;
    }
    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] = 1;
            }

            int answer = findCabbage(graph);
            System.out.println(answer);
        }


    }
}

 

가장 처음에는 Scanner로 배추가 있는지/없는지를 입력 받아서 graph 이중 배열에 저장해놓고 -> 

저장한 배열에서 상하좌우 인덱스를 설정해서 찾은 후 ->

찾은 것을 기반으로 최소한으로 필요한 배추벌레의 수를 찾는 거라고 생각했었다.

 

고려해야 할 부분은 크게 2가지 였다.

 

1. 가령 [1][1] 자리에 배추가 있어서 여기에 배추벌레를 놓고 상하좌우를 살피면 [0,1] [1,0], [2,1], [1,2] 이렇게 찾아서 배추벌레가 모두 없는 0이라면 배추벌레를 추가하겠지만 만약 배추벌레가 [2,1]에 있는 상황이여서 그래프가 [2][1] 자리를 탐색할 때 이전 공간에 인접해 있기에 카운트를 제외하는 건 어떻게 구현할 것인가에 대한 문제와

2. 이렇게 for문을 돌면서 모든 배추벌레를 탐색을 한다면 M*N의 시간이 걸리지 않을까? 하는 생각도 들었다. (이건 추측, 그런데 밭을 뒤지면서 배추를 찾아야 하니까 어쩔 수 없을 거 같다는 생각이 들기도 한다....)

 

예시에 나와있던 심어진 배추 예시

그래서 만약 탐색을 하던 도중에 배추가 있는 자리인 graph[x][y] = 1 이 나왔을 경우를 중심으로 생각해보기로 했다. 

가령 1이 있는 경우를 중심 노드로 생각하고 그래프 알고리즘 중 하나로 풀면 어떨까 하는 생각이 들었다.

 

다익스트라/플로이드/bfs/dfs/유니온 지금까지 했던 것들이 생각이 쭉 났었는데 다익스트라는 아무래도 우선 순위 큐에 넣고 작은 것 부터 꺼내는 작업이기에 1,0으로 이뤄진 상황에서는 적합하지 않은 거 같고, 플로이드는 인접한 노드까지 가는데에 사이 노드를 계산하는 것이니까 적합하지 않은 거 같고,,,

그래프에서 경로 탐색을 하는 유니온도 적합하지 않을거 같고, 더불어서 dp도 생각을 해보니 점화식을 사용하거나 for문을 사용해서 재귀로 풀어야 하는데 그럴 수 없을거 같다는 생각이 들었다,,,

 

결국에 남은 풀이는 BFS/DFS 중 하나로 풀 수 있는 방법인거 같다. 처음에 들었던 생각은 아무래도 배추벌레가 상하좌우로 옮겨 다니기 때문에 BFS(Breath First Search) 즉 넓이 우선 탐색을 쓰는 게 더 적절하지 않을까? 하는 생각이 들었다. BFS는 우선 순위 큐를 통해 구현했었고, 인접한 노드를 모두 큐에 넣고 하나씩 꺼내면서 방문하는 것이었다. 

 

이렇게 정리를 해놓고 보니까 일단 배추벌레에 대한 정보가 담겨진 graph를 탐색을 하면서 만약 1 곧 배추가 심겨져 있는 것이라면 상하좌우를 인접 노드라고 두고 x,y 클래스를 우선순위 큐에 선언할 때 에 넣은 후에 만약 탐색을 하면서 또 1이 발견 되었을 때 큐에 넣어져 있는 x,y를 체크하고 만약 체크가 되어 있지 않다면 배추 벌레를 추가하고 체크가 되어 있다면 큐에 있는 값을 꺼내는 식이 어떨까? 하는 생각이 들었다.

 

일단 푸는 방법을 생각해내었으니 대강 구현하자면 다음과 같다. 

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 findCabbage(int graph[][]) {
        int ans = 0;
        int dx[] = {1,0,-1,0};
        int dy[] = {0,-1,0,1};

        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) {
                    // 큐에 넣음
                    q.add(new Cabbage(i, j));
                    // 상하좌우를 살핌
                    for (int k = 0; k < 4; k++) {
                        int nx = i + dx[k];
                        int ny = j + dy[k];
                        // 벗어난 공간이라면 건너뜀.
                        if(nx<0|| ny<0|| nx>graph.length-1 || ny>graph[i].length-1) {
                            continue;
                        }
                        // 배추가 새로 심겨진 곳을 발견한다면?
                        if(graph[nx][ny] ==1 && q.poll().getX() != nx && q.poll().getY() != ny) {
                            q.add(new Cabbage(nx, ny));
                            ans += 1;
                        }

                    }
                }

            }
        }

        return ans;
    }
    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);
        }

    }
}