백준 JAVA 1012번 유기농 배추 DFS && BFS

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

1012번: 유기농 배추

문제의 내용과 테스트 케이스 입력이 길어보이지만 DFS와 BFS의 기본을 다루는 문제다.

 

배추가 심어져 있는 1과 연결되는 1을 하나의 구역이라고 생각하자.

 

Visited를 사용하지 않고 1을 방문했을 경우 0으로 바꾸고 for문에 진입한다.

 

 

 

---

 

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


public class Main {
    static int[][] map; // 배추 심는 곳
    static int d, c, min = Integer.MAX_VALUE;
    static int where;
    static int temp;
    static int[] x = {0, 0, 1, -1}, y = {1, -1, 0, 0}; // 상하좌우 이동으로 사용될 배열

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int t = Integer.parseInt(br.readLine());
        for (int i = 0; i < t; i++) {
            String[] s = br.readLine().split(" ");
            c = Integer.parseInt(s[0]);
            d = Integer.parseInt(s[1]);
            where = Integer.parseInt(s[2]);
            map = new int[c][d];
            for (int j = 0; j < where; j++) {
                int a, b;
                String[] s1 = br.readLine().split(" ");
                a = Integer.parseInt(s1[0]);
                b = Integer.parseInt(s1[1]);
                map[a][b] = 1;
            }
            for (int j = 0; j < c; j++) {
                for (int k = 0; k < d; k++) {
                    if (map[j][k] == 1) {
                        dfs(j, k);
                        temp++;
                    }
                }
            }
            min = temp;
            temp = 0;
            System.out.println(min);
        }
    }

    public static void dfs(int c1, int d1) {
        if (map[c1][d1] == 0) {
            return;
        }
        map[c1][d1]=0;

        for (int i = 0; i < 4; i++) {
            int i1 = c1 + x[i];
            int i2 = d1 + y[i];
            if (i1 >= 0 && i1 < c && i2 >= 0 && i2 < d) {
                dfs(i1, i2);
            }
        }
    }
}

---

BFS 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n, e, count, answer;
    static int [][] map;
    static boolean [][] visit;
    static int [] x={1,-1,0,0},y={0,0,-1,1};
    static Queue<int[] > queue = new LinkedList<>();
    public static void main(String args[]) throws IOException {

        int T = Integer.parseInt(br.readLine());
        for(int p=0; p<T; p++){
            String[] s = br.readLine().split(" ");
            e=Integer.parseInt(s[0]);
            n=Integer.parseInt(s[1]);
            count=Integer.parseInt(s[2]);
            map = new int [n][e];
            visit= new boolean[n][e];
            for(int i=0; i<count;i++){
                String[] s1 = br.readLine().split(" ");
                int x = Integer.parseInt(s1[0]);
                int y = Integer.parseInt(s1[1]);
                map[y][x]=1;
            }

            for(int i=0; i<n; i++){
                for(int j=0; j<e; j++){
                    if(map[i][j]==1 && !visit[i][j]){
                        bfs(i,j);
                        answer++;
                    }
                }
            }
            System.out.println(answer);
            answer=0;
        }
    }
    public static void bfs(int a, int b){
        queue.add(new int[] {a,b});

        while(!queue.isEmpty()){
            int[] poll = queue.poll();
            int px=poll[1];
            int py= poll[0];

            visit[py][px]=true;

            for(int i=0; i<4; i++){
                int nx = px+x[i];
                int ny = py+y[i];
                if(nx>=0 &&nx<e && ny>=0 && ny<n){
                    if(!visit[ny][nx] && map[ny][nx]==1){
                        queue.add(new int[] {ny,nx});
                        visit[ny][nx]=true;
                    }
                }
            }
        }
    }


}

 

 

시간 차이는 나지 않는 걸 볼 수 있다.