[백준] 14890 경사로

14890번: 경사로

 

www.acmicpc.net

풀이

시뮬레이션 문제이다. 모든 행과 열에 대해서 반대 방향으로 지나갈 수 있는지 확인하면 된다. 선형으로 탐색하며 경사로를 지을 수 있는지 확인하면 되는데, 이 때 경우는 총 4가지이다.

1. 이전 높이와 현재 높이가 같은 경우
2. 이전 높이가 현재 높이보다 1 높은 경우
3. 이전 높이가 현재 높이보다 1 낮은 경우
4. 모두 아닌 경우

1번의 경우 땅의 갯수를 증가시킨다.
2번의 경우 같은 높이인 땅의 길이가 l보다 짧으면 지나갈 수 없다
3번의 경우 현재 높이부터 l만큼 탐색하면서 높이 변화가 생기면 지나갈 수 없다
4번의 경우 항상 지나갈 수 없다

이 때 1, 2, 4의 경우는 어렵지 않게 구현할 수 있다. 3번의 경우를 조금 주의해야하는데 길이 l만큼 탐색을 한 뒤에 인덱스와 같은 높이의 갯수를 세기 위한 변수인 cnt를 잘 조정해야한다.

코드

#include <iostream>
#include <vector>
using namespace std;

int n, l, ans;
int map[100][100];

int row_check(int r) {
    int cnt = 1;
    int h = map[r][0];
    for (int i = 1; i < n; i++) {
        int cur = map[r][i];
        // 이전 높이와 현재 위치가 같은 경우
        if (h == cur) cnt++;
        else {
            // 이전 높이가 1 낮은 경우
            if (h + 1 == cur) {
                if (cnt < l) return 0;
                cnt = 1;
            }
            // 이전 높이가 1 높은 경우
            else if (h - 1 == cur) {
                for (int j = 0; j < l; j++) 
                    if (i + j >= n || map[r][i + j] != cur) return 0;
                i += (l - 1);
                cnt = 0;
            }
            // 둘 다 아닌 경우 불가능
            else return 0;
            h = cur;
        }            
    }
    return 1;
}

int col_check(int c) {
    int cnt = 1;
    int h = map[0][c];
    for (int i = 1; i < n; i++) {
        int cur = map[i][c];
        // 이전 높이와 현재 위치가 같은 경우
        if (h == cur) cnt++;
        else {
            // 이전 높이가 1 낮은 경우
            if (h + 1 == cur) {
                if (cnt < l) return 0;
                cnt = 1;
            }
            // 이전 높이가 1 높은 경우
            else if (h - 1 == cur) {
                for (int j = 0; j < l; j++)
                    if (i + j >= n || map[i + j][c] != cur) return 0;
                i += (l - 1);
                cnt = 0;
            }
            // 둘 다 아닌 경우 불가능
            else return 0;
            h = cur;
        }
    }
    return 1;
}

void simulation() {
    int ans = 0;
    for (int i = 0; i < n; i++)
        ans += (row_check(i) + col_check(i));
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> l;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> map[i][j];
    simulation();
    return 0;
}