백준 14890번 - 경사로

https://www.acmicpc.net/problem/14890

문제에 대한 설명이 굉장히 긴편에 속하는데

특별한 알고리즘을 적용하지 않고 문제를 이해한 뒤에 그대로 구현을 해주면 된다.

해결방법은 다음과 같다

1) 주어진 길에 대한 높이를 입력 받는다

   - 가로열과 세로열에 대한 길의 개수를 구하기 위해 2개의 2차원 배열을 사용했다.

2) 왼쪽부터 오른쪽방향으로 왼쪽 칸이 오른쪽 칸보다 클 때,

   오른쪽 칸이 1만큼 높이가 낮은지를 L의 길이만큼 비교한 후, 맞지 않다면 다른 행을 검사한다.

3) 2번 검사를 진행하면서, 만약 조건을 만족한다면 해당 위치에 경사로를 짓는다

4) 오른쪽부터 왼쪽 방향으로 2번과 동일하게 검사를 진행한다. (오른쪽 칸이 왼쪽보다 1만큼 큰지 확인)

 - 추가된 점은 2번에서 경사로를 지엇기 때문에 검사 위치에 경사로가 있다면 다른 행을 검사한다.

5) 행의 개수 만큼 2~4를 반복한다.

왼쪽과 오른쪽 방향으로 모두 검사를 진행하기 때문에 1만큼 차이가 나는 것을 설정할 때 

왼쪽과 오른쪽이 모두 1만큼 크다고 설정하고 검사를 하거나,

왼쪽과 오른쪽이 모두 1만큼 작다고 설정하고 검사를 진행해도 결과값은 똑같다.

조금 더 고민을 한 뒤에, 코드를 짧게 줄여야 될 것 같다..(코드가 너무 길다)

#include <iostream>
#include <vector>
using namespace std;
 
int cal(vector<vector<int>> map,int N,int L){
    
    int cnt=0;
    vector<vector<int>> hill(N+1,vector<int>(N+1,0)); //경사로 구간
    
    for(int i=1;i<=N;i++){
        
        bool check=true;
        
        //왼쪽에서 오른쪽 검사
        for(int j=1;j<N;j++){
            
            if(map[i][j]>map[i][j+1]){
                
                //범위 확인
                if(j+L>N){
                    check=false;
                    break;
                }
                
                //높이 차이 1 확인
                for(int k=j+1;k<=j+L;k++){
                    if(map[i][k]!=map[i][j]-1){
                        check=false;
                        break;
                    }
                    
                    hill[i][k]++; //높이 차이 1이면 경사로 짓는다
                }
                
                if(check==false)
                    break;
                
                j+=L-1;
            }
            
        }
        
        //왼쪽부터 검사했을 때 이상있으면 오른쪽부터 검사할 필요 x
        if(check==false)
            continue;
        
        //오른쪽에서 왼쪽으로 검사
        for(int j=N;j>1;j--){
            
            if(map[i][j]>map[i][j-1]){
                
                if(j-L<1){
                    check=false;
                    break;
                }
                
                for(int k=j-1;k>=j-L;k--){
                    
                    //높이 차이 안맞거나 경사로 이미 지은 구간일 때
                    if(map[i][k]!=map[i][j]-1 || hill[i][k]){
                        check=false;
                        break;
                    }
                }
                
                if(check==false)
                    break;
                
                j-=L-1;
            }
        }
        
        if(check)
            cnt++;
    }
    
    return cnt;
}
int main(){
    
    int N,L;
    cin>>N>>L;
    
    int ans=0;
    vector<vector<int>> horizon_road(N+1,vector<int>(N+1,0)); //(i,j)
    vector<vector<int>> vertical_road(N+1,vector<int>(N+1,0)); //(j,i)
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            scanf("%d",&horizon_road[i][j]);
            vertical_road[j][i]=horizon_road[i][j];
        }
    }
    
    ans+=cal(horizon_road, N, L);
    ans+=cal(vertical_road, N, L);
    
    cout<<ans<<endl;
    
    return 0;
}