BOJ 14890 - 경사로(시뮬레이션, 배열)

www.acmicpc.net/problem/14890

14890번: 경사로

- 2차원 지도의 row column을 왔다갔다하면서 검사를 하는게 힘들어서 행, 열을 따로 1차원 배열로 만들어서 검사하는 방식은 다른 블로그에서 팁을 얻었다.

- 일단 1차원 배열로 행이나 열을 가져오면 통하는 길인지를 검사하는 것이 쉬워진다.

1. 높이 차이가 나는 경우(경사로 오르막인 경우, 내리막인 경우를 따진다)

- 높이가 1  차이 나야한다.

- 경사로가 지도 밖으로 를 넘어가지 않는다

- 경사로가 놓이는 지점끼리는 높이 차이가 나지 않는다

이 3가지를 만족시키는 로직을 작성해야된다.

2. 높이 차이가 나지 않는 경우 - 통과

// boj 14890 경사로
#include <iostream>
#include <vector>
using namespace std;

const int MAX = 100;
int N, L;  // 100, 경사로길이100
vector<vector<int>> v(MAX, vector<int>(MAX));
vector<int> line(MAX);

// row, column에 대한 1차원 배열을 받아와서 검사
bool isPossible(vector<int>& line) {
    vector<bool> c(MAX);
    for (int i = 1; i < N; ++i) {
        if (line[i - 1] != line[i]) {                          // 높이 차이가 나는 경우
            if (abs(line[i] - line[i - 1]) > 1) return false;  // 1이상 차이나면 안됨

            if (line[i - 1] < line[i]) {  // 오르막
                for (int j = 1; j <= L; ++j) {
                    if (i - j < 0) return false;                   // 왼쪽으로 넘어가면 안됨
                    if (line[i - 1] != line[i - j]) return false;  // 경사로 지점간 높이 차이 있으면 안됨
                    if (c[i - j]) return false;                    // 경사로가 이미 놓여있으면 안됨
                    c[i - j] = true;
                }
            } else {  // 내리막
                for (int j = 0; j < L; ++j) {
                    if (i + j >= N) return false;
                    if (line[i] != line[i + j]) return false;
                    if (c[i + j]) return false;
                    c[i + j] = true;
                }
            }
        }
    }

    return true;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N >> L;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> v[i][j];
        }
    }

    int ans = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            line[j] = v[i][j];
        }

        if (isPossible(line)) ans++;
    }

    for (int j = 0; j < N; ++j) {
        for (int i = 0; i < N; ++i) {
            line[i] = v[i][j];
        }
        if (isPossible(line)) {
            ans++;
        }
    }

    cout << ans;
    return 0;
}