[문제 풀이] 백준 2468번 안전 영역 JAVA

문제

  문제접근 방법   

해당 문제는 N이 주어지고 N*N 크기의 배열 공간이 존재하다. 또 각각의 칸이 높이가 다르다고 할 때 비가 오면 잠기지 않고 남아있는 안전지대의 개수를 구하는 문제이다. 여기서 안전지역은 상하좌우로 연결되어 있으면 하나의 안전지역으로 취급한다.

처음에는 비가 얼마나 오는지 나와있지 않아서 N크기 그리고 N만큼의 비가 오는구나라고 이해하고 문제를 풀이하였다. 

운 좋게도? 예제에 나와있는 부분을 입력하면 같은 출력이 나오는 것을 확인하였다. 하지만 틀렸다는 결과를 받았고 문제를 자세히 분석해 본 결과 안전지대의 최대 개수 즉 , 1~ 지형의 최대 높이까지의 비가 오고 이때 안전지대의 최대 개수는 몇 개 이냐를 묻는 문제였다. 처음에는 당연히 2나 3만큼 비가 오는 게 덜 잠기니까 안전지대가 많지라고 인지했지만 안전지대의 넓이가 아닌 몇 개의 안전지대, 몇 개의 덩어리가 존재하냐는 문제였다. 그래서 코드를 아래와 같이 작성하였다.

 

 

< 초기 코드  >

import java.util.*;

public class Main{
    public static int safeZone[][];
    public static boolean visited[][];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int cnt=0;
        safeZone=new int[n][n];
        visited=new boolean[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                safeZone[i][j]=s.nextInt();
                if(safeZone[i][j]<=n)visited[i][j]=true;
            }
        }
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(!visited[i][j]){
                    cnt++;
                    dfs(i,j);
                }
            }
        }
        System.out.print(cnt);
    }
    public static void dfs(int x,int y){
        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&&nx<visited.length&&ny>=0&&ny<visited.length){
                if(!visited[nx][ny]){
                    visited[nx][ny]=true;
                    dfs(nx,ny);
                    visited[nx][ny]=false;
                }
            }
        }
    }
}

초키 코드는 문제를 잘못이해하여 비가 N만큼 왔을 때 안전지대가 몇 개인지?를 초점을 두고 문제를 풀이하였다. 

앞서 풀어보았던 섬 개수 구하기 문제처럼 dfs를 통해 코드를 구현하였고 입력받을 때 N보다 작거나 같은 경우는 이미 물에 잠긴 공간이니까 카운트할 필요 없어 방문처리를 하고 시작하는 방식으로 코드를 작성하였고 

이런 종류의 문제들이 결국 dfs함수가 몇 번 호출되었는지가 몇 개의 덩어리로 나누어져 있는지라고 볼 수 있어 dfs가 호출될 때마다 카운트해 주고 그 값을 출력하였다. 하지만 N높이만큼 비가 오는 것이 아닌 1부터 진행하여 언제가 최대 개수의 안전지역을 가지는지를 구하는 문제여서 아래와 같이 코드를 수정해 주었다.

< 최종 코드 1 >

import java.util.*;

public class Main{
    public static int safeZone[][];
    public static boolean visited[][];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int cnt=0;
        int maxCnt=0;
        int maxN=0;
        safeZone=new int[n][n];
        visited=new boolean[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                safeZone[i][j]=s.nextInt();
                maxN=maxN>safeZone[i][j]?maxN:safeZone[i][j];
            }
        }

        for(int t=1;t<maxN;t++){
            cnt=0;
            visited=new boolean[n][n];
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(!visited[i][j]&&safeZone[i][j]>t){
                        cnt++;
                        dfs(i,j,t);
                    }
                }
            }
            maxCnt=maxCnt>cnt?maxCnt:cnt;
        }
        
        System.out.print(maxCnt);
    }
    public static void dfs(int x,int y,int maxN){
        int dx[]={-1,1,0,0};
        int dy[]={0,0,-1,1};
        visited[x][y]=true;
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            
            if(nx>=0&&nx<visited.length&&ny>=0&&ny<visited.length){
                if(!visited[nx][ny]&&safeZone[nx][ny]>maxN){
                    visited[nx][ny]=true;
                    dfs(nx,ny,maxN);
                    
                }
            }
        }
    }
}

본 코드처럼 반복문을 통해 1부터 값을 비교하는 방식으로 재귀함수에 비가 온 높이를 매개변수로 전달하고 

safeZone [nx][ny]>maxN일 때만 dfs를 호출해 주게 구현하였다. 하지만 해당코드에도 문제점이 존재하였는데

바로 비가 오지 않을 때를 고려하지 못했다는 것이었다. 위에서부터 계속 비의 높이가 1부터 시작된다고 설명하였었는데

문제를 자세히 확인해 보면 맨 아래 노트 부분에 아무 지역도 물에 잠기지 않을 수도 있다.라는 문구를 확인해 볼 수 있다.

처음에는 이해도가지 않고 중요한 부분이 아니라 생각되어 별생각 없이 넘기고 문제를 구현하였는데

해당 부분이 비가 오지 않을 수도 있다는 것을 암시해 주는 부분이었다.

현 코드에서는 비의 높이가 1부터 시작하는데 비의 높이가 1부터 시작하려면 안전지대의 최대 개수를 저장하는 변수 maxCnt가 

0으로 초기화되는 것이 아니라 1로 초기화되어야 한다. 그래야 비가 오지 않을 때 안전지대의 수가 0이 아니라 1로 올바른 값이

출력될 수 있다. 아니면 비의 높이를 0부터 시작하면 maxCnt를 0으로 초기화하고 시작해도 문제없다.

아래 코드는 이 부분을 수정한 코드이다.

 

< 최종 코드 2 >

import java.util.*;

public class Main{
    public static int safeZone[][];
    public static boolean visited[][];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        int n=s.nextInt();
        int cnt=0;
        int maxCnt=0;
        int maxN=0;
        safeZone=new int[n][n];
        visited=new boolean[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                safeZone[i][j]=s.nextInt();
                maxN=maxN>safeZone[i][j]?maxN:safeZone[i][j];
            }
        }

        for(int t=0;t<maxN;t++){
            cnt=0;
            visited=new boolean[n][n];
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(!visited[i][j]&&safeZone[i][j]>t){
                        cnt++;
                        dfs(i,j,t);
                    }
                }
            }
            maxCnt=maxCnt>cnt?maxCnt:cnt;
            //System.out.println(cnt);
        }
        
        System.out.print(maxCnt);
    }
    public static void dfs(int x,int y,int maxN){
        int dx[]={-1,1,0,0};
        int dy[]={0,0,-1,1};
        visited[x][y]=true;
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            
            if(nx>=0&&nx<visited.length&&ny>=0&&ny<visited.length){
                if(!visited[nx][ny]&&safeZone[nx][ny]>maxN){
                    visited[nx][ny]=true;
                    dfs(nx,ny,maxN);
                    
                }
            }
        }
    }
}

위에서 이미 설명하였기 때문에 별도의 설명 없이 넘어가도록 하겠다.

 

  마무리  

해당 문제는 어렵지는 않았지만 비의 높이가 주어지지 않아 문제를 잘해 석해 야한 문제였다. 문제를 초반에 읽고 dfs로 탐색하는 문제라는 것을 인지한 후에도 문제를 끝까지 꼼꼼하게 분석했어야 하는데 그렇지 못해서 시간을 소비한 문제였다.

앞서 풀었던 섬의 개수, 미로 찾기 등과 유사한 풀이 방식을 지니는 문제라 생각되며 해당 문제가 어렵다고 느껴진다면 

앞선 문제들을 풀어보고 다시 풀어보는 것을 추천한다. 

 

  추가 코드 분석 및 풀이  

 

 

< 추가 코드 ver BigInteger + gcd 메서드 >

 

 

 참고 자료