[문제 풀이] 백준 14890번 경사로 JAVA

문제

  문제접근 방법   

해당 문제는 N x N 크기의 지도가 존재하고 각 칸마다 높이가 존재할 때 지나갈 수 있는 길의 개수를 확인하려고 한다. 

이때 지나갈 수 있는 길이란 한행 또는 한 열 전부를 나타내고 한쪽 끝에서 다른 쪽 끝까지 지나가는 것을 의미한다.

또 길을 지나갈수 있으려면 길의 높이가 같아야 한다. 길의 높이가 다르다면 경사로를 설치해서 지나갈 수 있는데

경사로의 조건은 아래와 같다.

• 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
• 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
• 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

또 아래와 같은 경우에는 경사로가 놓일 수 없다.

• 경사로를 놓은 곳에 또 경사로를 놓는 경우
• 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
• 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
• 경사로를 놓다가 범위를 벗어나는 경우

N과 L, 그리고 N x N 지도의 각각의 칸의 높이가 주어질 때 위의 조건을 만족하는 길의 수를 출력하는 프로그램을 작성하는 문제이다. 처음에는 어떤 방식으로 탐색할지 고민이 많았다. BFS로 탐색해야 하나도 생각했지만 범위가 애매해서 DFS로 바꾸어 생각해 보았다. 하지만 어떤 깊이나 명확한 조건이 없어 보여 다른 풀이를 고민했다. 마지막으로 풀이했던 문제 중 계단 오르기 문제에서도 선택하고 선택하지 않는 조건을 점화식으로 나타내 DP로 접근한 것이 기억나 DP도 고민해 보았지만 가능하다고 해도 DP를 한 줄마다 사용하고 각 행 N개 열 N개를 모두 탐색하면 복잡도가 말도 안 되게 늘어날 것 같아 단순 구현 문제라 판단 조건에 맞게 아래와 같이 코드를 작성하였다.

 

 

< 초기 코드  >

import java.util.*;

public class Main{
    public static int map[][];
    public static int cnt=0;
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int l=s.nextInt();
        map=new int[n][n];
        boolean visited[]=new boolean[n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                map[i][j]=s.nextInt();
            }
        }
        int len=l;
        for(int i=0;i<n;i++){
            len=l;
            int breakN=0;
            int continueN=0;
            int seqN=0;
            Arrays.fill(visited,false);
            for(int j=1;j<n;j++){
                if(map[i][j]-map[i][j-1]>1||map[i][j-1]-map[i][j]>1){
                  breakN++;
                  break;
               }
                if(continueN==1&&len>0){
                   len--;
                   visited[j]=true;
                   continue;
               }
               if(len==0){continueN=0;len=l;}
               if(map[i][j]!=map[i][j-1]){
                   if(map[i][j]-map[i][j-1]==1||map[i][j-1]-map[i][j]==1){
                       if(map[i][j]<map[i][j-1]){
                           seqN=0;
                           int count=1;
                           for(int k=1;k<l;k++){
                               if(j+k<n&&map[i][j+k]==map[i][j]){
                                   count++;
                               }
                               else{break;}
                           }
                           if(count!=l){breakN++;break;}
                           else{continueN=1;}
                       }
                       else{
                           if(seqN+1<l||visited[j]){
                               breakN++;
                               break;
                           }
                           
                       }
                       
                       
                   }
                   
               }
               else{
                   seqN++;
                   
               }
               
               
            }
            if(breakN==0)cnt++;
        }
        //System.out.print(cnt);
        len=l;
        for(int i=0;i<n;i++){
            len=l;
            int breakN=0;
            int continueN=0;
            int seqN=0;
            Arrays.fill(visited,false);
            for(int j=1;j<n;j++){
                if(map[j][i]-map[j-1][i]>1||map[j-1][i]-map[j][i]>1){
                  breakN++;
                  break;
               }
                if(continueN==1&&len>0){
                   len--;
                   visited[j]=true;
                   continue;
               }
               if(len==0){continueN=0;len=l;}
               if(map[j][i]!=map[j-1][i]){
                   if(map[j][i]-map[j-1][i]==1||map[j-1][i]-map[j][i]==1){
                       if(map[j][i]<map[j-1][i]){
                           seqN=0;
                           int count=1;
                           for(int k=1;k<l;k++){
                               if(j+k<n&&map[j+k][i]==map[j][i]){
                                   count++;
                               }
                               else{break;}
                           }
                           if(count!=l){breakN++;break;}//이부분이 같으면 연속인데 연속일때 패싱하는 분기가 필요요
                           else{continueN=1;}
                       }
                       else{
                           if(seqN+1<l||visited[j]){
                               breakN++;
                               break;
                           }
                       }
                       
                       
                   }
               }
               else{
                   seqN++; 
               }
               
               
            }
            if(breakN==0)cnt++;
        }
        
        
        
        
        System.out.print(cnt-1);
        
    }
}

전체적인 코드의 흐름은 값을 입력받고 각 행과 열을 따로 분리해서 반복문을 진행해주었다. 행과 열의 틀 자체는 같으므로 행 기준으로 설명을 이어가겠다. 코드 진행 흐름은 아래와 같다.

1. 현재 위치에서 바로 이전 칸과의 차를 구한다.
   1. 차 값이 1보다 큰 경우는 breakN을 증가시키고 반복을 종료 시킨다.
      1. breakN이 0이 아닌 경우는 길이 아닌 경우로 간주된다.
   2. 차 값이 1인 경우
      1. 현재 칸의 값이 이전 칸의 값보다 큰지 작은 지를 판단하다. 
         1. 크다면 오르막 로직을 실행한다.
            1. 오르막 로직은 현재 값 기준으로 이전값이 L개만큼만 존재한다면 경사로 설치가 가능하므로 seqN을 통해서 경사로가 설치되지 않는 경우 seqN을 증가시켜주었다.
            2. 이후 seq와 l을 이용하여 l보다 seqN이 작다면 경사로 설치가 불가능하므로 breakN을 증가시켜 주었다.
               
               1. breakN이 0이 아닌 경우는 길이 아닌 경우로 간주된다.
         2. 작다면 내리막 로직을 실행한다.
            1. 내리막 로직은 현재 값과 이전값을 비교해 1이라면 현재 값부터 +l 한 값까지를 비교해 값이 같다면 count를 증가시켜 준다.
            2. count가 l과 같다면 경사로 설치가 가능하고 아니라면 breakN을 증가시켜 준다.
               1. breakN이 0이 아닌 경우는 길이 아닌 경우로 간주된다.
            3. 경사로 설치가 가능하다면 방문처리를 위해 continueN을 1로 초기화해준다.
         3. 이후 반복에서 continueN=1이고 len>0이라면 countinue 예약어를 통해 반복문을 스킵해 주었다.
            1. len값을 감소시켜 준다
            2. visited [j]=true로 바꾸어 방문처리를 해준다.
            3. continue를 통해 스킵해 준다.
         4. 이를 반복해 준다.

하지만 이런 방식에는 2가지 문제가 존재하였다. continue를 통해 방문처리를 해주는 방식은 나중에 문제가 발생할 수 있고 

정확성이 떨어진다는 점과 오르막과 내리막 둘 다 방문처리를 하는 방식이 아닌 하나만 선택해서 방문처리를 해주기 때문에 

모든 경우를 보장할 수 없다는 것이다.

처음에는 map에 담겨 있는 각각의 높이가 존재하고 한쪽 방향으로 진행한다고 했을 때 내리막 오르막 둘 중 하나만 신경 쓰면 된다고 생각했다. 이게 무슨 말이냐면 오르막이든 내리막이든 겹치면 안 되니까 하나만 경사로가 설치되었는지 아닌지를 판단해 주는 방식으로 코드를 작성하였다. 하지만 이것은 틀린 판단이었다. 내리막끼리 겹칠 수도 있는 것이고 오르막 내리막도 l=1인경우 충분히 겹칠 수가 있는 것이다. 해당 문제를 아래와 같이 해결하였다.

< 최종 코드 >

import java.util.*;

public class Main{
    public static int map[][];
    public static int cnt=0;
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int l=s.nextInt();
        map=new int[n][n];
        boolean visited[]=new boolean[n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                map[i][j]=s.nextInt();
            }
        }
        for(int i=0;i<n;i++){
            int breakN=0;
            Arrays.fill(visited,false);
            for(int j=1;j<n;j++){
                if(map[i][j]-map[i][j-1]>1||map[i][j-1]-map[i][j]>1){
                  breakN++;
                  break;
               }

               
               if(map[i][j]!=map[i][j-1]){
                   if(map[i][j]-map[i][j-1]==1||map[i][j-1]-map[i][j]==1){
                       if(map[i][j]<map[i][j-1]){
                           int count=0;
                           for(int k=0;k<l;k++){
                               if(j+k<n&&map[i][j+k]==map[i][j]&&!visited[j+k]){
                                   count++;
                               }
                               else{break;}
                           }
                           if(count!=l){breakN++;break;}
                           else{
                               for(int k=0;k<l;k++){
                                   visited[j+k]=true;
                           }
                               
                           }
                       }
                       else{
                           int count=0;
                           for(int k=0;k<l;k++){
                               if(j-k-1>=0&&map[i][j-k-1]==map[i][j-1]&&!visited[j-k-1]){
                                   count++;
                               }
                               else{break;}
                           }
                           if(count!=l){breakN++;break;}
                           else{
                               
                               for(int k=0;k<l;k++){
                                   if(j-k-1>=0){
                                       visited[j-k-1]=true;
                                   }
                                   else{breakN++;
                                        break;
                                       
                                   }
                                }
                           }
                           
                       }
                       
                       
                   }
                   
               }

            }
            if(breakN==0)cnt++;
        }
        for(int i=0;i<n;i++){
            int breakN=0;
            Arrays.fill(visited,false);
            for(int j=1;j<n;j++){
                if(map[j][i]-map[j-1][i]>1||map[j-1][i]-map[j][i]>1){
                  breakN++;
                  break;
               }
               
               if(map[j][i]!=map[j-1][i]){
                   if(map[j][i]-map[j-1][i]==1||map[j-1][i]-map[j][i]==1){
                       if(map[j][i]<map[j-1][i]){
                           int count=0;
                           for(int k=0;k<l;k++){
                               if(j+k<n&&map[j+k][i]==map[j][i]&&!visited[j+k]){
                                   count++;
                               }
                               else{break;}
                           }
                           if(count!=l){breakN++;break;}//이부분이 같으면 연속인데 연속일때 패싱하는 분기가 필요요
                           else{
                               for(int k=0;k<l;k++){
                                   visited[j+k]=true;
                           }
                               
                           }
                       }
                       else{
                           int count=0;
                           for(int k=0;k<l;k++){
                               if(j-k-1>=0&&map[j-1-k][i]==map[j-1][i]&&!visited[j-k-1]){
                                   count++;
                               }
                               else{break;}
                           }
                           if(count!=l){breakN++;break;}
                           else{
                               
                               for(int k=0;k<l;k++){
                                   if(j-k-1>=0){
                                       visited[j-k-1]=true;
                                   }
                                   else{breakN++;
                                        break;
                                       
                                   }
                                }
                           }
                           
                       }
                       
                       
                   }
               }
               
               
            }
            if(breakN==0)cnt++;
        }
        
        
        
        
        System.out.print(cnt);
        
    }
}

 

먼저 위에서는 count를 증가시켜서 방문처리를 해주어 실제로 방문 처리를 해주는 visited가 존재하지만 역할이 애매했다. 

이를 count와 continue를 제거하고 visited에 확실한 역할을 주는 방향으로 수정해 주었다.

그러기 위해서는 count를 증가시켜 경사로 설치가 가능하다면 continue를 통해 넘어가는 방식이 아니라 visited를 true 처리해 주고

이후에 visited를 통해 너 방문했어? 를 물어보는 형식으로 코드를 수정해 주었다.

또 내리막에서만 경사로 설치를 위해 L 만큼이 존재하는지 판단하는 것이 아니라 오르막에서도 해주었다.

초기 코드처럼 작성한다면 경사로가 설치되지 않은 것뿐이지 L만큼의 길이가 같은 높이인 것을 보장할 수없다 그래서 코드를 위처럼 수정해 주었다. 또 오르막은 내리막과 다르게 현재위치부터가 아니라 현재위치-1로 작성해야함을 인지해 그부분도 수정해주었다.

  마무리  

해당 문제는 어려워 보였지만 실제로는 별다른 알고리즘이 필요하지 않고 분기를 나누어주고 조건을 성립하게 만들어주는 구현 문제였다. 본인이 작성했을 때는 코드도 길고 시간도 조금 걸려서 실제 코딩테스트에 나오면 조금 어려울 수도 있을 것이라고 판단했다.

실제로 초기코드가 맞은 것이 아니라 오류가 발생해 이를 해결하기 위해 추가 코드를 작성하기도 했기에 시간제한이 있는 코딩 테스트를 위해서는 연습이 필요하다 생각했다.

  추가 코드 분석 및 풀이  

다른 블로거 분들이나 코드를 작성하신 분들의 풀이를 확인해 보았지만 알고리즘을 적용했다거나 풀이의 틀자체가 다르다고 생각되는 풀이는 없어 추가 풀이는 하지 않도록 하겠다.