[DFS/BFS] 백준 1012번 유기농 배추(Java)

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

1012번: 유기농 배추

📚 문제

한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다. 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다.

1	1	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	0	0	1	0	0	0	0	0
0	0	1	1	0	0	0	1	1	1
0	0	0	0	1	0	0	1	1	1

각 테스트 케이스에 대해 필요한 최소의 배추흰지렁이 마리 수를 출력하시오.

 

📝 문제 해결

시작 지점에서 상하좌우를 살펴본 뒤 인접한 땅 중 배추가 심어져있는 땅(1)이 있다면 0으로 바꾸고 

더이상 인접한 지점에 배추가 심어져있는 땅(1)이 없다면 배추흰지렁이 개수 +1 해준다.

 

💻 코드

• DFS (깊이 우선 탐색)

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

public class Main{
    static int M, N, K;
    static int map[][] = new int[50][50];

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

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

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

            int cnt = 0;
            for(int i=0; i<M; i++){
                for(int j=0; j<N; j++){
                    if(dfs(i,j)) cnt += 1;
                }
            }

            System.out.println(cnt);

        }
    }

    public static boolean dfs(int x, int y){
        if(x<0 || x>=M || y<0 || y>=N) return false;
        if(map[x][y]==1){
            map[x][y]=0;
            dfs(x-1,y);	//상
            dfs(x+1,y);	//하
            dfs(x,y-1);	//좌
            dfs(x,y+1);	//우
            return true;
        }

        return false;
    }
}

 

• BFS (너비 우선 탐색)

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

public class Main{
    static int M, N, K;
    static int map[][] = new int[50][50];
    static int[] dx = { 0, -1, 0, 1 };
	static int[] dy = { 1, 0, -1, 0 };

    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        for(int tc=0; tc<T; tc++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());

            for(int k=0; k<K; k++){
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                map[x][y] = 1;
            }
            
            int cnt = 0;
            for(int i=0; i<M; i++){
                for(int j=0; j<N; j++){
                    if(map[i][j]==1) {
                        bfs(i,j);
                        cnt += 1;
                    }
                }
            }
            
            System.out.println(cnt);
            
        }
    }
    
    public static void bfs(int x, int y){
        Queue<int[]> que = new LinkedList<>();
        que.offer(new int[]{x,y});
        map[x][y]=0;
        
        while(!que.isEmpty()){
            int[] now = que.poll();
            
            for(int i=0; i<4; i++){
                int nx = now[0] + dx[i];
                int ny = now[1] + dy[i];
                
                if(nx>=0 && nx<M && ny>=0 && ny<N && map[nx][ny]==1){
                    map[nx][ny] = 0;
                    que.offer(new int[]{nx,ny});
                } 
            }
            
        }
    }
}

 

💡 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 활용한 문제 유형/응용

DFS, BFS은 특징에 따라 사용에 더 적합한 문제 유형들이 있습니다.

• 그래프의 모든 정점을 방문하는 것이 주요한 문제
  단순히 모든 정점을 방문하는 것이 중요한 문제의 경우 DFS, BFS 두 가지 방법 중 어느 것을 사용하셔도 상관없습니다.
  둘 중 편한 것을 사용하시면 됩니다.
• 경로의 특징을 저장해둬야 하는 문제
  예를 들면 각 정점에 숫자가 적혀있고 a부터 b까지 가는 경로를 구하는데 경로에 같은 숫자가 있으면 안 된다는 문제 등, 각각의 경로마다 특징을 저장해둬야 할 때는 DFS를 사용합니다. (BFS는 경로의 특징을 가지지 못합니다)
• 최단거리 구해야 하는 문제
  미로 찾기 등 최단거리를 구해야 할 경우, BFS가 유리합니다.
  왜냐하면 깊이 우선 탐색으로 경로를 검색할 경우 처음으로 발견되는 해답이 최단거리가 아닐 수 있지만,
  너비 우선 탐색으로 현재 노드에서 가까운 곳부터 찾기 때문에경로를 탐색 시 먼저 찾아지는 해답이 곧 최단거리기 때문입니다.

이밖에도

• 검색 대상 그래프가 정말 크다면 DFS를 고려
• 검색대상의 규모가 크지 않고, 검색 시작 지점으로부터 원하는 대상이 별로 멀지 않다면 BFS

[출처 : https://velog.io/@lucky-korma]