백준 1012 유기농 배추 - JAVA

1012 문제 링크

---

https://www.acmicpc.net/problem/1012

 

문제 설명

---

 

입출력

---

 

코드

---

< DFS >

import java.io.*;
import java.util.*;
 
public class Main {
    static int[][] graph;
    static boolean[][] visit;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int M;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            
            graph = new int[M][N];
            visit = new boolean[M][N];
            
            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine());
                int X = Integer.parseInt(st.nextToken());
                int Y = Integer.parseInt(st.nextToken());
                graph[X][Y] = 1;
            }
            
            int result = 0;
            for (int j = 0; j < M; j++) {
                for (int k = 0; k < N; k++) {
                    if (graph[j][k] == 1 && !visit[j][k]) {
                        dfs(j, k);
                        result++;
                    }
                } 
            }
            bw.write(String.valueOf(result) + "\n");
        } 
        bw.flush();
    }
    
    private static void dfs(int X, int Y) {
        visit[X][Y] = true;
        
        for (int i = 0; i < 4; i++) {
            int nx = X + dx[i];
            int ny = Y + dy[i];
            if(nx >= 0 && ny >= 0 && nx < M && ny < N) {
                if (graph[nx][ny] == 1 && !visit[nx][ny]) {
                    dfs(nx, ny);    
                }
            }
        }
    }
}

 

< BFS >

import java.io.*;
import java.util.*;
 
public class Main {
    static int[][] graph;
    static boolean[][] visit;
    static int[] dx = {0, 0, -1, 1};
    static int[] dy = {1, -1, 0, 0};
    static int M;
    static int N;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            int K = Integer.parseInt(st.nextToken());
            
            graph = new int[M][N];
            visit = new boolean[M][N];
            
            for (int j = 0; j < K; j++) {
                st = new StringTokenizer(br.readLine());
                int X = Integer.parseInt(st.nextToken());
                int Y = Integer.parseInt(st.nextToken());
                graph[X][Y] = 1;
            }
            
            int result = 0;
            for (int j = 0; j < M; j++) {
                for (int k = 0; k < N; k++) {
                    if (graph[j][k] == 1 && !visit[j][k]) {
                        bfs(j, k);
                        result++;
                    }
                } 
            }
            bw.write(String.valueOf(result) + "\n");
        } 
        bw.flush();
    }
    
    private static void bfs(int X, int Y) {
        visit[X][Y] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {X, Y});
        while(!queue.isEmpty()) {
            int[] current = queue.poll();
            for (int i = 0; i < 4; i++) {
                int nx = current[0] + dx[i];
                int ny = current[1] + dy[i];
                if(nx >= 0 && ny >= 0 && nx < M && ny < N) {
                    if (graph[nx][ny] == 1 && !visit[nx][ny]) {
                        queue.offer(new int[] {nx, ny});
                        visit[nx][ny] = true;
                    }
                }
            }
        }
    }
}

 

 

알고리즘 설명

---

기존 dfs, bfs 문제들과 유사한 문제입니다. 배추는 1칸만 심어져있더라도 지렁이가 있기 때문에, graph[0][0] 부터 시작해서 graph[N][M] 까지 2중 반복문으로 배추가 있고, 방문하지 않은 곳(visit[X][Y] = false)을 발견하면 dfs / bfs로 해당 배추와 연결된 모든 배추를 방문처리합니다. 이후 배추의 군집 개수(result)를 1 증가시킵니다. 누적된 result의 값이 해당 밭의 필요한 지렁이의 개수입니다.
 
연결된 배추의 방문처리는 문제에도 나와있듯이 상하좌우에 위치한 배추가 서로 인접한 것이라고 했으므로, dx[]와 dy[]로 X, Y의 상하좌우의 움직임을 주어 인접한 배추를 찾게 합니다.

 

코드 해석

---

 입력으로 T(테스트 케이스 수)를 받아, 각 테스트 케이스마다 배추밭 크기(M x N)와 배추의 위치(K개)를 입력받습니다.
이후, 배추의 위치를 2차원 배열 graph[][]에 저장합니다. graph[0][0] 부터 graph[M-1][N-1]까지 이중 반복문으로 배추가 있는 위치(1)이면서 방문하비 않은 곳을 발견하면 DFS 또는 BFS 탐색을 수행합니다. 탐색이 시작될 때마다 result 변수를 1 증가시켜, 지렁이가 필요한 배추 군집의 개수를 계산합니다. 모든 탐색이 끝나면 result를 출력합니다.