[BOJ 1012] 유기농 배추 (Java, 그래프 탐색)

 

---

문제 링크

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

1012번: 유기농 배추

---

풀이

- 전형적인 격자형 그래프 탐색 문제 

- 방문 배열과 배추가 심어져 있는 배열을 가지고 그룹 카운트 수행 

- 방문하지 않고, 배추가 심어져 있는 경우 카운터를 하나 올리고 상하좌우 탐색하면서 방문처리

- Test Case별 시간복잡도 : O(N^2)

---

제출 코드

 

DFS의 경우

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int T, M, N, K, CNT;

    static int[][] FIELD;
    static boolean[][] VISIT;

    static int[][] DIRECTION = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        T = Integer.parseInt(st.nextToken()); // 테스트 케이스
        while(T > 0) {
            st = new StringTokenizer(br.readLine());

            M = Integer.parseInt(st.nextToken()); // 가로 길이
            N = Integer.parseInt(st.nextToken()); // 세로 길이
            K = Integer.parseInt(st.nextToken()); // 배추 심어진 위치 개수

            FIELD = new int[M][N];
            VISIT = new boolean[M][N];

            for(int i = 1; i <= K; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                FIELD[x][y] = 1;
            }

            pro();

            T -= 1;
        }
    }

    static void dfs(int x, int y) {
        VISIT[x][y] = true;

        for(int i = 0; i < 4; i++) {
            int nx = x + DIRECTION[i][0];
            int ny = y + DIRECTION[i][1];

            if(nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
            if(VISIT[nx][ny]) continue;
            if(FIELD[nx][ny] == 0) continue;

            dfs(nx, ny);
        }
    }

    static void pro() {
        CNT = 0;
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < N; j++) {
                if(!VISIT[i][j] && FIELD[i][j] == 1) {
                    CNT += 1;
                    dfs(i, j);
                }
            }
        }
        sb.append(CNT).append("\n");
    }

    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb);
    }
    
}

 

BFS의 경우

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

public class Main {
    
    static StringBuilder sb = new StringBuilder();

    static int T, M, N, K, CNT;

    static int[][] FIELD;
    static boolean[][] VISIT;

    static int[][] DIRECTION = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        T = Integer.parseInt(st.nextToken()); // 테스트 케이스
        while(T > 0) {
            st = new StringTokenizer(br.readLine());

            M = Integer.parseInt(st.nextToken()); // 가로 길이
            N = Integer.parseInt(st.nextToken()); // 세로 길이
            K = Integer.parseInt(st.nextToken()); // 배추 심어진 위치 개수

            FIELD = new int[M][N];
            VISIT = new boolean[M][N];

            for(int i = 1; i <= K; i++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                FIELD[x][y] = 1;
            }

            pro();

            T -= 1;
        }
    }

    static void bfs(int startX, int startY) {
        Queue<Integer> que = new LinkedList<>();
        que.add(startX);
        que.add(startY);
        VISIT[startX][startY] = true;

        while(!que.isEmpty()) {
            int x = que.poll(), y = que.poll();

            for(int i = 0; i < 4; i++) {
                int nx = x + DIRECTION[i][0];
                int ny = y + DIRECTION[i][1];

                if(nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
                if(VISIT[nx][ny]) continue;
                if(FIELD[nx][ny] == 0) continue;

                VISIT[nx][ny] = true;
                que.add(nx);
                que.add(ny);
            }
        }
    }

    static void pro() {
        CNT = 0;
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < N; j++) {
                if(!VISIT[i][j] && FIELD[i][j] == 1) {
                    CNT += 1;
                    bfs(i, j);
                }
            }
        }
        sb.append(CNT).append("\n");
    }

    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb);
    }
}