[문제 풀이] 백준 17086번 아기 상어 2 JAVA

문제

  문제접근 방법   

해당 문제는 N x M 크기의 공간에 아기 상어가 여러 마리 존재한다고 할 때 어떤 칸의 안전거리를 그 칸과 가장 거리가 가까운 아기 상어와의 거리라고 한다. 이동은 좌우상하 대각선 모두 가능하다고 한다면 안전거리의 최댓값이 몇인지를 출력하는 프로그램을 작성하는 문제이다.

먼저 문제를 읽자마자 bfs를 활용하여 어떤 칸에서 상어에 도달할 수 있는 칸의 최소값을 구하고 그 최솟값들 중에서 최댓값을 구하면 되는 문제라고 이해해 아래와 같이 코드를 작성하였다.

 

 

< 초기 코드  >

import java.util.*;

public class Main{
    public static int ocean[][];
    public static int safeDistance=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 max=-1;
        ocean=new int[n][m];
        visited=new boolean[n][m];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                ocean[i][j]=s.nextInt();
            }
        }
        
        for(int i=0;i<n;i++){
            
            for(int j=0;j<m;j++){
                if(!visited[i][j]&&ocean[i][j]==0){
                    int temp=sharkDetector(i,j);
                    max=max>temp?max:temp;
                }
            }
        }
        //bfs를 통해서 최소 거리에 존재하는 상어를 찾는다. 이값을 저장하는 방식으로 진행 
        System.out.println(max);
    }
    public static int sharkDetector(int x,int y){
        Queue<int[]> loc=new LinkedList<>();
        visited=new boolean[ocean.length][ocean[0].length];
        int cnt=0;
        loc.offer(new int[]{x,y,cnt});
        visited[x][y]=true;
        int dx[]={-1,1,0,0,-1,-1,1,1};
        int dy[]={0,0,-1,1,-1,1,-1,1};
        boolean breakN=false;
        
        while(!loc.isEmpty()){
            int xyz[]=loc.poll();
            for(int i=0;i<8;i++){
                int nx=xyz[0]+dx[i];
                int ny=xyz[1]+dy[i];
                if(nx>=0&&ny>=0&&nx<ocean.length&&ny<ocean[0].length){
                    if(ocean[nx][ny]==1){
                         breakN=true;
                         cnt=xyz[2]+1;
                         break;
                    }
                    if(!visited[nx][ny]){
                        visited[nx][ny]=true;
                        loc.offer(new int[]{nx,ny,xyz[2]+1});
                    }
                    
                }
            }
            if(breakN)break;
        }
        
        return cnt;
    }
}

위에서 설명하였듯이 작성한 코드이다. bfs를 활용하여 각각의 칸에서 상어까지의 최소거리를 측정하고 이후 최대값을 출력하는 방식이다. 하지만 해당 코드에서는 심각한 문제가 발생하였다. 방문처리로 인해 모든 칸의 최소거리를 측정하지 않는다는 점이 문제였다. 그래서 아래와 같이 코드를 수정하였다.

< 최종 코드 >

import java.util.*;

public class Main{
    public static int ocean[][];
    public static int safeDistance=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 max=-1;
        ocean=new int[n][m];
        visited=new boolean[n][m];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                ocean[i][j]=s.nextInt();
            }
        }
        
        for(int i=0;i<n;i++){
            
            for(int j=0;j<m;j++){
                if(ocean[i][j]==0){
                    int temp=sharkDetector(i,j);
                    max=max>temp?max:temp;
                }
                // else{
                //     System.out.print("s ");
                // }
            }//System.out.println();
        }
        //bfs를 통해서 최소 거리에 존재하는 상어를 찾는다. 이값을 저장하는 방식으로 진행 
        System.out.println(max);
    }
    public static int sharkDetector(int x,int y){
        Queue<int[]> loc=new LinkedList<>();
        visited=new boolean[ocean.length][ocean[0].length];
        int cnt=0;
        loc.offer(new int[]{x,y,cnt});
        visited[x][y]=true;
        int dx[]={-1,1,0,0,-1,-1,1,1};
        int dy[]={0,0,-1,1,-1,1,-1,1};
        boolean breakN=false;
        
        while(!loc.isEmpty()){
            int xyz[]=loc.poll();
            for(int i=0;i<8;i++){
                int nx=xyz[0]+dx[i];
                int ny=xyz[1]+dy[i];
                if(nx>=0&&ny>=0&&nx<ocean.length&&ny<ocean[0].length){
                    if(ocean[nx][ny]==1){
                         breakN=true;
                         cnt=xyz[2]+1;
                         break;
                    }
                    if(!visited[nx][ny]){
                        visited[nx][ny]=true;
                        loc.offer(new int[]{nx,ny,xyz[2]+1});
                    }
                    
                }
            }
            if(breakN)break;
        }
        //System.out.print(cnt+" ");
        return cnt;
    }
}

주석처리한 부분으로 모든 칸을 탐색하지 않는다는것을 알게 되었고 어차피 반복문을 통해 모든 칸을 탐색하고 최단거리를 구하는 것이기 때문에 bfs안에서가 아닌 main의 반복문에서는 별도의 방문처리가 필요하지 않아 if에서 제외시켜서 코드를 완성하였다.

 

  마무리  

처음에는 아기상어 문제를 생각하고 들어와서 문제를 풀었고 아기상어 문제는 고생한 기억이 있어 해당 문제도 어려울줄 알았지만

생각보다는 손쉽게 해결한 문제중 하나였다. 대각선 처리와 bfs만 잘 활용한다면 어렵지 않게 문제 해결이 가능할 것이라고 생각된다.