[BOJ 14890] 경사로

N X N 크기의 맵에 가로 N개 세로 N 개를 더해서 총 2N 개의 길이 있다. 각 지점에는 숫자가 써 있는데 높이를 나타낸다. 숫자가 같은 곳만 이동할 수 있는데 여기에서 경사로가 주어진다. 길이 L , 높이는 1로 고정되어있다. 경사로의 갯수는 무한하며 이 경사로들을 적절히 활용해 지나갈 수 있는 길의 갯수를 출력한다. 제약조건은 문제에 명시되어 있다.

문제 풀이 : 한 행, 한 열 씩 뜯어서 제약 조건에 위배가 되면 false 를 return 하는 check 함수 만들어 정답을 찾아냈다.

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
 
int N;
 
bool check(vector <int> &n, int L) {
    vector <bool> c(N, false);
 
    for (int i = 0; i < N-1; i++) {
        if (n[i] == n[i + 1]) continue;
 
        if (abs(n[i] - n[i + 1]) != 1) return false;
 
        if (n[i] > n[i + 1]) {
            for (int j = 1; j <= L; j++) {
                if (i + j >= N) return false;
 
                if (n[i + j] != n[i + 1]) return false;
 
                if (c[i + j]) return false;
 
                c[i + j] = true;
            }
        }
        else {
            for (int j = 1; j <= L; j++) {
                if (i + 1 - j < 0) return false;
                
                if (n[i + 1 - j] != n[i]) return false;
 
                if (c[i + 1 - j]) return false;
 
                c[i + 1 - j] = true;
            }
        }
    }
    return true;
}
int main() {
    cin >> N;
    int L;
    cin >> L;
 
    vector <vector <int> > map(N, vector <int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
    int ans = 0;
    for (int i = 0; i < N; i++) {
        vector <int> garo;
        for (int j = 0; j < N; j++) {
            garo.push_back(map[i][j]);
        }
        if (check(garo, L)) ans++;
    }
 
    for (int j = 0; j < N; j++) {
        vector <int> sero;
        for (int i = 0; i < N; i++) {
            sero.push_back(map[i][j]);
        }
        if (check(sero, L)) ans++;
    }
    
    
    cout << ans << '\n';
    return 0;
}