백준 #14890 경사로

백준 #14890 경사로

길이가 L, 높이가 1인 무한 개의 경사로를 갖고 지나갈 수 있는 행과 열의 개수를 구하는 구현 문제.

각각의 행 또는 열을 루프를 돌며 검사하여 길을 만들 수 있는지 확인한다.

1. 높이가 2 이상 차이가 나는 인접 칸이 있을 경우 false.
2. 높이가 1이상 차이가 나는 경우
   • 낮은 쪽의 길이 L만큼 검사, 범위를 벗어나거나, 높이가 다른 곳이 있거나, rampExists가 true인 경우(이미 경사로가 존재) false.
   • 모두 통과했다면 bool[] rampExists 배열에 true 저장.
3. 높이 차이가 없거나 경사로를 설치할 수 있을 경우 true

#include <iostream>
#include <bits/stdc++.h>
#include <memory.h>
#include <vector>

using namespace std;

int N, L;
int board[100][100];


vector<int> makeVector(int lineNum, bool isRow) {
    vector<int> v(N);
    for(int i = 0; i < N; i++) {
        if(isRow) {
            v[i] = board[lineNum][i];
        }
        else {
            v[i] = board[i][lineNum];
        }
    }
    return v;
}

bool lineIsGood(vector<int> v) {
    bool * rampExists = new bool[N];
    memset(rampExists, 0, sizeof(rampExists));
    for(int i = 1; i < N; i++) {
        if(abs(v[i] - v[i - 1]) > 1) {
            return false;
        }
        if(abs(v[i] - v[i - 1]) == 1) {
            if(v[i] > v[i - 1]) {
                for(int j = i - L; j < i; j++) {
                    if(j < 0 || v[j] != v[i - 1] || rampExists[j]) {
                        return false;
                    }
                }
                for(int j = i - L; j < i; j++) {
                    rampExists[j] = true;
                }
            }
            else {
                for(int j = i; j < i + L; j++) {
                    if(j >= N || v[j] != v[i] || rampExists[j]) {
                        return false;
                    }
                }
                for(int j = i; j < i + L; j++) {
                    rampExists[j] = true;
                }
            }
        }
    }
    delete[] rampExists;
    return true;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> L;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> board[i][j];
        }
    }
    int count = 0;
    for(int i = 0; i < N; i++) {
        if(lineIsGood(makeVector(i, true))) {
            count++;
        }
        if(lineIsGood(makeVector(i, false))) {
            count++;
        }
    }
    cout << count;
    return 0;
}