[문제 풀이] 백준 1012번 유기농 배추 JAVA

문제

  문제접근 방법   

해당 문제는 유기농 배추 밭이 있는데 농약을 쓰지 않고 배추를 해충으로 보호하면서 재배해야 한다. 

그래서 농약 대신 해충 방지에 효과적인 배추흰지렁이를 구입해 밭에 풀어넣으려한다. 이때 지렁이 한 마리가 있으면 서로 인접해 있는 배추로 이동가능해 해충으로 보호받을 수가 있다고 한다면 필요한 최소 지렁이 수를 구하는 프로그램을 작성하는 문제이다.

문제를 읽고는 배추 그룹을 구하면 최소갯수를 구할 수 있겠다고 판단했다. 배추그룹이라고 하면 이상하게 들릴 수도 있자만

땅그룹, 섬이라고 생각한다면 이해가 쉬울 것이라고 생각한다. 배추흰색지렁이는 인접한 상하좌우로 이동하면서 해충을 처리해 주니까 연결된 있는 곳에는 하나의 지렁이만이 필요한 것이다. 

이 문제 역시 dfs와 bfs 모두 풀이가 가능하다. 여기서 본인의 BFS/DFS 문제 풀이를 읽어보았던 분들이라면 의문이 들었을 수도 있다. 최소 지렁이 수를 구하라고했고 최소면 BFS로만 접근해 문제를 풀이해야 하는 것이 아니냐?라는 의문이다. 

앞서 그런식으로 설명했던 이유는 BFS가 최소 경로를 구할 때 사용되는 것은 맞고 최소, 최단을 요구하는 문제에서 BFS를 사용하지 않으면 풀이가 불가능한 문제들도 있기에 그런 식으로 말을 했었다. 이경우도 BFS로 해결이 가능하기 때문에 보편적으로 그렇게 말한 것이다. 하지만 BFS만 가능하고 DFS는 안된다는 식의 이해는 이 정도 수의  문제를 풀이 보았다면 조금 아쉽다고 생각한다.

BFS를 사용해야하는 이유는 최소/최단이라고 했지만 해당문제에서 최소가 어떤 탐색에서 경로상 최소가 아니고 벌레의 최소 개수이다. 여기서 최소 벌레라는 부분을 섬의 개수(벌레는 상하좌우로 이동하기 때문에)라고 해석해 보면 경로상 최소가 아니라 섬의 개수를 구하는 문제이므로 두 풀이 모두 가능하다는 것을 확인해 볼 수 있다.

위에서 계속 설명을 이해했다면 해당 문제가 섬의 개수문제와 유사한 문제라고 생각할 수 있다.  

 

< 최종 코드 >

import java.util.*;

public class Main{
    public static int cnt;
    public static boolean visited[][];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int test=s.nextInt();
        for(int t=0;t<test;t++){
            int n=s.nextInt();
            int m=s.nextInt();
            int k=s.nextInt();
            cnt=0;
            visited=new boolean[n][m];
            int cabbage[][]=new int[n][m];
            for(int i=0;i<k;i++){
                int y=s.nextInt();
                int x=s.nextInt();
                cabbage[y][x]=1;
            }
            for(int i=0;i<n;i++){
                for(int j=0;j<m;j++){
                    if(!visited[i][j]&&cabbage[i][j]==1){
                         bfs(i,j,cabbage);
                         cnt+=1;
                    }
                }
            }
            System.out.println(cnt);
        }
    }
    public static void bfs(int i,int j,int cabbage[][]){
        Queue<int[]> q=new LinkedList<>();
        q.offer(new int[]{i,j});
        visited[i][j]=true;
        int x[]={0,0,-1,1};
        int y[]={-1,1,0,0};
        while(!q.isEmpty()){
            int xy[]=q.poll();
            for(int k=0;k<4;k++){
                int nx=xy[1]+x[k];
                int ny=xy[0]+y[k];
                
                if(nx>=0&&nx<cabbage[0].length&&ny>=0&&ny<cabbage.length){
                    if(!visited[ny][nx]&&cabbage[ny][nx]==1){
                        visited[ny][nx]=true;
                        q.offer(new int[]{ny,nx});
                    }
                }
            }
            
            
        }
        
    }
}

풀이 또한 변수명을 제외한 모든 부분이 섬의 개수 풀이와 유사하므로 코드를 보고 이해가 가지 않는다면 

아래 링크를 통해 섬의 개수 풀이를 이해해보고 본인이 다시 한번 풀어보기를 추천한다.

섬의 개수

[문제 풀이] 백준 4963번 섬의 개수 JAVA

문제의 핵심은 최소 벌레 개수를 섬의 개수라고 해석할 수 있느냐 없느냐인 것 같다, 해석하지 못해도 풀리기도 하고 BFS와 DFS 풀이 성능 차이도 크게 없지만 나중에 다른 문제에서 이를 파악할 수 있는가 없는가로 문제를 해결이 가능하기 때문에 

이 차이를 이해하고 가면 좋을 것 같다.

 

 

  마무리  

해당 문제는 위에서 계속해서 설명하였듯이 섬의 개수 문제와 유사하고 본인이 느끼기에 BFS와 DFS를 단지 최소라는 단어로만 구분할 수 있는 사람들에게 BFS로만 접근이 가능하다고 유도하는 느낌을 받았다. 하지만 BFS/DFS 모두 풀이가 가능한 문제이므로 

문제를 잘해석해 어떤 문제에 어떤 알고리즘을 사용가능한지를 판단해야 한다.

  추가 코드 분석 및 풀이  

위에서 언급하였듯이 최소이지만 문제에서 요구하는 것은 개수이기 때문에 dfs로도 문제 풀이가 가능하다.

아래는 dfs로 작성한 코드이다.

< 추가 코드 ver DFS >

import java.util.*;

public class Main{
    public static boolean visited[][];
    public static int field[][];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        StringBuilder sb=new StringBuilder();
        
        int t=s.nextInt();
        for(int i=0;i<t;i++){
            int n=s.nextInt();
            int m=s.nextInt();
            int k=s.nextInt();
            int cnt=0;
            visited=new boolean[n][m];
            field=new int[n][m];

            for(int j=0;j<k;j++){
                int x=s.nextInt();
                int y=s.nextInt();
                field[x][y]=1;
            }
            for(int j=0;j<n;j++){
                for(int l=0;l<m;l++){
                    if(!visited[j][l]&&field[j][l]!=0){
                        dfs(j,l);
                        cnt++;
                    }
                }
            }sb.append(cnt).append("\n");
        }
        System.out.print(sb);
  
    }
    public static void dfs(int x,int y){
        if(visited[x][y]||field[x][y]==0){
            return;
        }
        
        visited[x][y]=true;
        int dx[]={-1,1,0,0};
        int dy[]={0,0,-1,1};
        
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx>=0&&ny>=0&&nx<visited.length&&ny<visited[0].length){
                dfs(nx,ny);
            }
        }
    }
}

위에서 이미 많은 설명을 했기 때문에 별도의 설명을 하지는 않겠다.