[JAVA] 백준 1012번: 유기농 배추

백준

[JAVA] 백준 1012번: 유기농 배추

스파게티 코더 2024. 7. 31. 23:35

문제

2차원 배열로 0이 빈 곳, 1이 배추가 있는 곳으로 주어지고, 배추를 해충으로부터 보호하려고 한다.
배추가 심어진 곳에 배추흰지렁이를 배치해 해충을 예방할 수 있으며, 상하좌우로 연결된 배추 모두를 보호할 수 있다.
이때, 필요한 배추흰지렁이의 최소 마리 수를 구하는 문제.

아이디어

그래프 탐색을 통해 연결된 노드 가지의 수를 구한다.
DFS 혹은 BFS 탐색을 시도해, 연결된 노드 가지 수를 카운트한다.
2차원의 visited 배열을 선언하기 싫어서, 배추 부분을 발견함과 동시에 0(false)으로 바꿔 다시는 탐색하지 못하게 했다.

풀이(DFS)

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

public class Main {
    static int N, M, K;
    // 상하좌우 이동 구현을 위한 배열 선언
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] graph;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

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

            graph = new boolean[N][M];
            
            // 배추 위치 체크
            for(int k=0; k<K; k++) {
                st = new StringTokenizer(br.readLine());
                graph[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = true;
            }

            int answer = 0;
            // 배추가 심겨져 있으면 탐색
            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    if(graph[i][j]) {
                        dfs(i, j);
                        answer++;
                    }
                }
            }
            sb.append(answer).append('\n');
        }
        System.out.println(sb);
    }

    static void dfs(int x, int y) {
        // 상하좌우 움직이며 배추가 있는지 체크
        for(int i=0; i<4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            // 그래프 범위를 벗어나면 continue
            if(nx<0 || ny<0 || nx>=N || ny>=M) {
                continue;
            }
            // 배추가 있다면, 배추를 0(false)으로 바꾸고 다시 탐색
            if(graph[nx][ny]) {
                graph[nx][ny] = false;
                dfs(nx, ny);
            }
        }
    }
}

풀이(BFS)

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

public class Main {
    static int N, M, K;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static boolean[][] graph;
    
    // bfs에 사용할 큐 선언
    static Deque<int[]> queue;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());

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

            queue = new ArrayDeque<>();
            graph = new boolean[N][M];

            for(int k=0; k<K; k++) {
                st = new StringTokenizer(br.readLine());
                graph[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = true;
            }

            int answer = 0;
            for(int i=0; i<N; i++) {
                for(int j=0; j<M; j++) {
                    if(graph[i][j]) {
                        queue.addLast(new int[]{i,j});
                        bfs();
                        answer++;
                    }
                }
            }
            sb.append(answer).append('\n');
        }
        System.out.println(sb);
    }

    static void bfs() {
        while(!queue.isEmpty()) {
            int[] tmp = queue.removeFirst();
            int x = tmp[0];
            int y = tmp[1];
            for(int i=0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx<0 || ny<0 || nx>=N || ny>=M) {
                    continue;
                }
                // 배추가 있다면, 해당 좌표를 큐에 넣고 반복
                // 배추는 0(false)으로 변경
                if(graph[nx][ny]) {
                    graph[nx][ny] = false;
                    queue.addLast(new int[]{nx,ny});
                }
            }
        }
    }
}

채점 결과

기타

DFS와 BFS 모두 큰 메모리, 실행시간 차이는 없었다.
배추흰지렁이는 사실 존재하지 않는 가상의 벌레라고 한다...
애초에 지렁이가 벌레를 어떻게 잡아먹..

문제 링크

1012번: 유기농 배추 (acmicpc.net)