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

💡문제 분석 요약

배추를 심은 배추밭의 정보를 입력받아, 배추가 모여있는 곳이 몇 군데인지(최소의 배추흰지렁이 수) 출력하는 문제이다.

• 시간 제한: 1초
• 메모리 제한: 512MB

 

💡알고리즘 설계

• `boolean[][] land` 에 배추가 있는 경우 true, 없는 경우 false로 설정한다.
• `land` 를 순회하며 배추가 있을 경우
  • 해당 위치를 false로 설정하고 `count` 를 증가시킨다.
  • 해당 위치로 dfs 메서드를 호출한다.
• dfs 메서드
  • 해당 위치의 상하좌우를 순회하여 배추가 있을 경우
    • 해당 위치를 false로 설정한다.
    • 해당 위치로 dfs 메서드를 재귀 호출한다.

 

💡코드

import java.io.*;

public class Main {
    static boolean[][] land;
    static int m, n, k, x, y;
    static int count;
    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};

    static void dfs(int i, int j) {
        for(int t=0; t<4; t++) {
            int cx = dx[t] + i;
            int cy = dy[t] + j;
            if(cx >= 0 && cx < m && cy >= 0 && cy < n && land[cx][cy]) {
                land[cx][cy] = false;
                dfs(cx, cy);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        while(t-- > 0) {
            String[] info1 = br.readLine().split(" ");
            m = Integer.parseInt(info1[0]);
            n = Integer.parseInt(info1[1]);
            k = Integer.parseInt(info1[2]);
            land = new boolean[m][n];
            for(int i=0; i<k; i++) {
                String[] info2 = br.readLine().split(" ");
                x = Integer.parseInt(info2[0]);
                y = Integer.parseInt(info2[1]);

                land[x][y] = true;
            }

            count = 0;
            for(int i=0; i<m; i++) {
                for(int j=0; j<n; j++) {
                    if(land[i][j]) {
                        land[i][j] = false;
                        count++;
                        dfs(i, j);
                    }
                }
            }

            System.out.println(count);
        }
    }
}

 

💡시간복잡도

배추밭의 모든 위치를 순회하기 때문에 $O(N*M)$이다.

 

💡 다른 풀이

BFS 메서드로도 구현할 수 있었다.

static void bfs(int i, int j) {
    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[] {i, j});

    while(!q.isEmpty()) {
        int[] a = q.poll();

        for(int t=0; t<4; t++) {
            int cx = dx[t] + a[0];
            int cy = dy[t] + a[1];

            if(cx >= 0 && cx < m && cy >= 0 && cy < n && land[cx][cy]) {
                q.offer(new int[] {cx, cy});
                land[cx][cy] = false;
            }
        }
    }
}

 

💡 느낀점 or 기억할정보

DFS를 인접 행렬로 해결하는 것은 어느 정도 감을 잡은 것 같다.