백준 14890 - 경사로

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

14890번: 경사로

문제 설명

---

N (지도의 행,열의 크기)

L (경사로의 길이)

경사로가 다음과 같이 주어졌을때, 행,열 기준으로 경사로의 조건이 충족되는 개수를 탐색을 진행한다.

위의 예를들어 N,L (6,2)인 경우, [222323]일때 [222323] 에서 경사로의 길이가 1인 상태에서 내리막이 진행되므로 성립되지 않는다.

다른 예시로 [223332]인 경우에도, [223332]에서 마지막 부분에서 내리막 경사로의 길이가 1로 마무리가 되므로 조건에 성립하지 않는다.

 

이처럼 문제에서는 다음과 같은 조건을 성립해야한다.

1. 오르막,내리막이 진행될때 높이의 차이는 2이상이 되면 안된다.

2. 경사로 설치할때, 경사로가 서로 겹치면 안된다.

(즉, 내리막 경사로 설치중 오르막 경사로 설치가 진행되어선 안되고, 오르막 경사로 설치중 내리막 경사로 설치가 진행되어선 안된다.)

3. 시작과 마지막 점도 반드시 경사로 조건에 성립되어야 한다.

 

 

접근 방법

---

평지, 오르막, 내리막 경사로 설치 및 진행중이라는 변수를 만들어 수시로 check 해야한다.

1. 먼저 high >=2 (조건 불능)

2. 내리막 OR 오르막 경사로 진행중에 오르막 OR 내리막 경사로 설치 (조건 불능)

 

before_road : 오르막 경사로가 설치가 가능하도록 이전의 평지의 개수를 세는 변수 

after_road : 내리막 경사로가 설치가 가능하도록 현재 위치 다음부터 평지의 차감해 나가는 변수

자세한 설명은 주석을 통해 확인하시면 더 쉽게 이해가능합니다~

 

 

코드 

---

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int map[101][101];
int rotate_map[101][101];
int n,l;
int ans=0;

//가로,세로를 나누지 않고 모두 확인하기 위해 
//90도 회전을 진행하여 search 함수를 공용으로 사용하도록함
void copy(){
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            rotate_map[i][j]=map[j][n-i-1] ; 
        }
    }
}
void search(int map[][101]){
    for(int i=0;i<n;i++){
    	//한줄씩 확인할때 마다 초기화 진행
        int before_road=0;
        int after_road=0;
        int road_high=0;
        //중간에 조건에 어긋난 경우 chk
        bool result=true;
        for(int j=0;j<n;j++){
            if(j==0){
            	//초기 init
                road_high=map[i][j];
                before_road=1;after_road=0;
            }
            else{
                //평지 OR 오르막 OR 내리막
                if(abs(road_high-map[i][j])<=1){
                    if(road_high == map[i][j]){
                        //내리막 경사로가 완성되지 않은 경우 
                        if(after_road!=0){
                            after_road--;
                            continue;
                        }//내리막 경사로가 완성된 경우(after_road==0)
                        else{
                            before_road++;continue;
                        }
                    }
                    //내리막...
                    else{ 
                        //내리막이 진행되면서 이전 내리막 경사로 설치가 완료된 경우
                        if(road_high > map[i][j]&&after_road==0){
                        	//이미 내리막이 진행되었으므로 l-1을 더해준다.
                            after_road+=l-1;
                            before_road=0;
                            //내리막이 진행되면 길이만큼 평지가 존재해야하므로 road_high 변경
                            road_high=map[i][j];
                        }
                        //오르막...
                        else{
                        	//오르막이 진행되면서 내리막 경사로 설치가 완료된 경우
                            if(before_road>=l&&after_road==0){
                                before_road=1;
                                road_high=map[i][j];
                                continue;
                            }
                            //아닌경우
                            else{result=false;break;}
                        }
                    }
                }
                //high가 2 이상 차이날 경우 
                else{result=false;break;}
            }
        }
        //search가 끝난후에 경사로 조건에 어긋난 경우 
        if(after_road!=0){continue;}
        else{
            if(result){ans++;}
        }
    }
}
int main(){
    cin>>n>>l;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++) cin>>map[i][j];
    }
    //search...
    search(map);
    //copy...
    copy();
    //search...
    search(rotate_map);
    //result...
    cout<<ans<<"\n";
}

funny algorithm ^0^~