[문제 풀이] 백준 1743번 음식물 피하기 JAVA

문제

  문제접근 방법   

해당 문제는 제목 그대로 음식물 피하는 것이 목적이고 모든 음식물을 피하기는 어려우니 작은 것들 말고 큰 음식물 쓰레기(음식물 근처에 음식물이 있으면 뭉치게 되어 큰 음식물 쓰레기가 된다.)만 피해 가려고 할 때 어떤 음식물의 크기가 가장 큰지를 출력하면 되는 문제이다.

처음 문제를 읽고 섬의 개수를 구하는 문제에 조건이 하나 추가된 형태라는 생각이 들었다.

섬의 개수 문제에서는 상하죄우로 연결된 섬의 개수를 구하는 문제였지만 해당 문제에서는 각각 어떤 섬이 있는지 섬의 개수를 탐색하는 과정은 유사하지만 섬의 개수가 아닌 가장 큰 섬을 구하는 것이 목표여서 이 과정만 하나 추가해 문제를 해결하였다.

 

< 최종 코드 >

import java.util.*;

public class Main{
    public static int count=0;
    public static boolean visited[][];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int m=s.nextInt();
        int k=s.nextInt();
        int map[][]=new int[n+1][m+1];
        visited=new boolean[n+1][m+1];
        for(int i=0;i<k;i++){
            int y=s.nextInt();
            int x=s.nextInt();
            map[y][x]=1;
        }
        int max=0;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(!visited[i][j]&&map[i][j]==1){
                    bfs(i,j,map);
                    max=max<count?count:max;
                    count=0;
                }
                
            }
        }
        System.out.print(max);
    }
    
    public static void bfs(int i,int j,int map[][]){
        Queue<int[]> q=new LinkedList<>();
        q.offer(new int[]{i,j});
        count++;
        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 ny=xy[0]+y[k];
                int nx=xy[1]+x[k];
                
                if(nx>=0&&nx<map[0].length&&ny>=0&&ny<map.length){
                    if(!visited[ny][nx]&&map[ny][nx]==1){
                        visited[ny][nx]=true;
                        count+=1;
                        //System.out.println("ss"+count);
                        q.offer(new int[]{ny,nx});
                    }
                }
            }
            
        }
        
    }
}

 코드의 흐름은 다른 bfs 코드들과 다를 것이 없다. 여기서 핵심은 count를 통해서 섬을 탐색할때 섬의 크기를 측정하고

if(! visited [i][j]&&map [i][j]==1){
                    bfs(i,j,map);
                    max=max<count?count:max;
                    count=0;
                }

해당 식에서 max=max<count?count:max;를 통해 max값을 계속 갱신해 섬 중 최대 섬의 크기를 저장하는 것이다.

다른 코드들도 존재하지만 visited를 통한 방문처리 , x [], y [] 배열을 활용한 상하좌우 이동, Queue를 통한 인접한 좌표 저장등은 정석적인 bfs코드와 같아 자세하게 설명하지는 않겠다.

 

  마무리  

앞서 여러번 언급하였지만 bfs문제든 dfs문제던지 최솟값이 필요한 경우가 아니라면 dfs로 풀리면 bfs로 풀린다.

그래서 기본적인 문제에 약간의 조건들을 추가한 문제가 많다고 생각한다. 만약 해당 문제를 푸는데 어려움이 있었다면

• 섬의 개수
• 미로 탐색

위의 문제를 다시 풀어보거나 풀이를 통한 이해를 하고 넘어가기를 추천한다. 아주 기본적인 문제여서 해당 부분을 이해하지 못한다면 이후 응용이 추가된 문제에서 더 어려울 것이라 생각된다.

 

  추가 코드 분석 및 풀이  

해당 문제는 최소값을 요구하는 문제가 아니므로 당연하게도 dfs로도 풀이가 가능하다, 아래는 dfs 코드이다. 

 

< 추가 코드 ver BFS >

- 추후 업데이트 예정