백준(BOJ) 14890 경사로 **

# 시뮬레이션

코드 구현이 조금 길었을 뿐, 실수만 하지 않는다면 어렵지는 않다.

# 풀이

1. 우선 입력을 같은 높이 끼리 묶어준다. { 높이, 연속 된 갯수 }

ex ) 3 3 2 2 1 1 1 -> {3,2} {2,2} {1,3}으로 변환

2. 앞에 높이와 비교하면서 높이 1이아니거나 낮은 높이가 L보다 작으면 못 가는 길

ex1 ) {3,3} {1,3} -> 높이 차이가 1이 아닌 경우

ex2 ) L=2 일 때, {3,3} {2,1} or {2,1} {3,3} -> 낮은 쪽이 L보다 작은 경우 (순서 상관 x)

ex3 ) L=2 일 때, {3,3} {2,2} {3,3} ->  낮은 쪽의 갯수를 L씩 빼준다.

{3,3} {2,2} {3,3} (가능)-> {3,3} {2,0} {3,3} (불가능) 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <limits.h>
#include <string.h>
#include <string>
#include <sstream>
#define MAX 105
#define INF 2123456789
 
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n,m,ans=0,map[MAX][MAX];
 
// 경사길 확인
int Find(vector<pi> v)
{
    for(int i=1;i<v.size();i++)
    {
        pi &test=v[i-1].first<v[i].first?v[i-1]:v[i];
        // 높이가 1차이 나거나, 낲은 쪽이 L보다 작은경우 못가는 길
        if(test.second<m||abs(v[i-1].first-v[i].first)!=1)
            return 0;
        test.second-=m;
    }
    return 1;
}
// 3 3 2 2 1 1 1 -> {3,2} {2,2} {1,3}으로 변환
vector<pi> Grouping(vector<int> v)
{
    vector<pi> ret;
    int cur=v[0],cnt=1;
    for (int i = 1; i < n; i++)
    {
        if(cur!=v[i]) {
            ret.push_back({cur, cnt});
            cur=v[i],cnt=1;
        }
        else
            cnt++;
    }
    ret.push_back({cur,cnt});
    return ret;
}
int main(){
    // 입력
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++) {
        for (int j = 0; j < n; j++)
            scanf("%d", &map[i][j]);
    }
 
    for(int i=0;i<n;i++){
        vector<int> v1,v2;
        for(int j=0;j<n;j++)
        {
            v1.push_back(map[i][j]);
            v2.push_back(map[j][i]);
        }
        ans+=(Find(Grouping(v1))+Find(Grouping(v2)));
    }
    printf("%d",ans);
    return 0;
}