백준[14890] - 경사로

문제

백준 14890 문제 보기

접근 방법

다소 예외처리가 많은 구현 문제였다. 문제는 오르막, 내리막 길을 설치하기 위해서는 바닥이 높이차이가 1이나고 L만큼의 바닥이 확보되어야한다는데서 문제를 접근했다.

• checkC, checkR 함수를 통해 특정 열 또는 행에서부터 주어진 수 만큼 같은 높이로 되어있는지, 이미 오르막 또는 내리막이 설치되어있는지 확인한다.
• establishC, establishR를 활용해 경사를 설치했다고 chk 배열에 표시한다.
• 경사로를 설치하면 내가 밟고 있는 발판의 위치 +1 또는 -1하고 다시 check를 반복한다.

코드

#include <iostream>
#include <cstring>

using namespace std;

int N, L;
int chk[101][101];
int arr_copy[101][101];

bool checkR(int r, int c, int cnt) {
    int start = arr_copy[r][c];
    if(c < 0) return false;
    for(int i = c; i < c+cnt; i ++) {
        if(start != arr_copy[r][i] || chk[r][i] == 1){
            return false;
        }
    }
    return true;
}

bool checkC(int r, int c, int cnt) {
    int start = arr_copy[r][c];
    if(r < 0) return false;
    for(int i = r; i < r+cnt; i ++) {
        if(start != arr_copy[i][c] || chk[i][c] == 1){
            return false;
        }
    }
    return true;
}

void establishRow(int r, int c, int cnt) {
    for(int i = c; i < c+cnt; i ++) {
        chk[r][i] = 1;
    }
}

void establishColumn(int r, int c, int cnt) {
    for(int i = r; i < r+cnt; i ++) {
        chk[i][c] = 1;
    }
}

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

    int cnt = 0;
    for(int r = 0; r < N; r ++) {
        if(checkR(r, 0, N)) {
            cnt++;
        } else {
            int startHeight = arr_copy[r][0];
            for(int c = 0; c < N; c ++) {
                if(startHeight != arr_copy[r][c]) {
                    if(startHeight - arr_copy[r][c] == 1) {
                        // 내리막 길이 체크
                        if(checkR(r, c, L)) {
                            establishRow(r, c, L);
                            c += L - 1;
                            startHeight --;
                        } else {
                            break;
                        }
                    } else if(startHeight - arr_copy[r][c] == -1) {
                        if(checkR(r, c - L, L)) {
                            startHeight ++;
                        } else {
                            break;
                        }
                    } else {
                        break;
                    }
                }
                if(startHeight == arr_copy[r][c] && c == N - 1) {
                    cnt ++;
                }
            }
        }
    }

    memset(chk, 0, sizeof(chk));

    for(int c = 0; c < N; c ++) {
        if(checkC(0, c, N)) {
            cnt++;
        } else {
            int startHeight = arr_copy[0][c];
            for(int r = 0; r < N; r ++) {

                if(startHeight != arr_copy[r][c]) {
                    if(startHeight - arr_copy[r][c] == 1) {
                        // 내리막 길이 체크
                        if(checkC(r, c, L)) {
                            establishColumn(r, c, L);
                            r += L - 1;
                            startHeight --;
                        } else {
                            break;
                        }
                    } else if(startHeight - arr_copy[r][c] == -1) {
                        if(checkC(r - L, c, L)) {
                            startHeight ++;
                        } else {
                            break;
                        }
                    } else {
                        break;
                    }
                }
                if(startHeight == arr_copy[r][c] && r == N - 1) {
                    cnt ++;
                }
            }
        }
    }
    cout << cnt;
}