백준 14890번 경사로

문제 링크 : https://www.acmicpc.net/problem/14890

문제 접근

1. 코드 작성을 편하게 하기 위해 2차원배열에 들어있는 값들을 한줄씩 살펴 볼때마다, 한줄을 1차원배열에 복사하여 지나갈 수 있는 길인지 체크하였다.

2. 체크하는 과정은 우선 한길에 속한 모든 칸의 높이가 같은지를 먼저 확인하고 만약 모든칸의 높이가 같다면 지나갈 수 있는 길로 판단하였다.

3. 이후엔 복사해놓은 배열을 앞에서 뒤로 탐색하며 인접 칸의 높이 차이를 구하였다.

높이의 차이가 2이상이면 지나갈수 없는길로 판단했다.

높이의 차이가 1이라면 차이가 나기 시작한 점부터 l만큼의 길이에 있는 점들이 같은 높이 인지 판단하였다.

만약 l만큼길이의 점들중 다른 높이가 하나라도 있다면 지나갈수 없는 길로 판단했다.

l만큼의 길이의 점들이 모두 같은 높이라면 오른쪽아래로 내려가는 경사로를 놓았다.

경사로를 놓는 것은 bool 배열을 이용하여 해당 인덱스의 값을 true로 바꾸어 주었다.

4. 3번과 마찬가지로 뒤에서 앞으로 탐색하며 지나갈수있는길인지 경사로를 놓을수 있는지를 판단한 후 왼쪽 아래로 내려가는 경사로를 놓았다.

왼쪽아래로 내려가는 경사로도 마찬가지로 다른 bool 배열을 이용하여 체크하였다.

5. 오른쪽 아래로 내려가는 경사로와 왼쪽 아래로 내려가는 경사로를 체크한 두 배열을 비교하며 경사로가 겹치는 부분이 있으면 지나갈수 없는길로 판단하였다.

겹치는 부분이 없으면 지나갈 수 있는길로 판단하였다.

6. 모든 길에 대해 1번~5번의 과정을 거치며 지나갈수 있는길인지 없는 길인지를 판단하며 지나갈수 있는 길의 경우 그 수를 세어 마지막에 출력하였다.

소스코드

#include <iostream>
 
using namespace std;
 
int map[100][100];
int clonline[100];
int n, l, cnt = 0;
 
bool rgsr[100];
bool lgsr[100];
 
bool isSameHeight(int s, int e) {
    for (int i = s; i < e; i++) {
        if (clonline[i] != clonline[i + 1]) {
            return false;
        }
    }
    return true;
}
 
void inspection(int ay, int ax, int by, int bx) {
    // 클론 배열 복사
    if (ay == by) {
        // y좌표 같음 가로로 봄.
        for (int i = 0; i < n; i++) {
            clonline[i] = map[ay][i];
        }
    }
    else if (ax == bx) {
        // x좌표 같음 세로로 봄.
        for (int i = 0; i < n; i++) {
            clonline[i] = map[i][ax];
        }
    }
 
    // 1. 높이 다 같은 경우
    if (isSameHeight(0, n - 1)) {
        cnt++;
        return;
    }
 
    // 경사로 배열 초기화
    for (int i = 0; i < n; i++) {
        rgsr[i] = false;
        lgsr[i] = false;
    }
 
    int differ;
 
    //앞에서 뒤로 탐색
    for (int i = 0; i < n-1; i++) {
        differ = clonline[i] - clonline[i + 1];
        if (differ > 1) {
            return;
        }
        else if (differ == 1) {
            int e = i + l;
            if (e >= n)
                return;
 
            if (isSameHeight(i + 1, e)) {
                // 경사로 설치
                for (int j = i + 1; j <= e; j++) {
                    rgsr[j] = true;
                }
            }
            else {
                return;
            }
        }
    }
 
    //뒤에서 앞으로 탐색
    for (int i = n - 1; i > 0; i--) {
        differ = clonline[i] - clonline[i - 1];
        if (differ > 1)
            return;
        else if (differ == 1) {
            int s = i - l;
            if (s < 0)
                return;
 
            if (isSameHeight(s, i - 1)) {
                //경사로 설치
                for (int j = s; j <= i - 1; j++) {
                    lgsr[j] = true;
                }
            }
            else {
                return;
            }
        }
    }
 
    for (int i = 0; i < n; i++) {
        if (rgsr[i] && lgsr[i]) {
            return;
        }
    }
 
    cnt++;
 
}
 
int main()
{
    cin >> n >> l;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> map[i][j];
 
 
    for (int i = 0; i < n; i++) {
        inspection(i, 0, i, n - 1);
    }
 
    for (int j = 0; j < n; j++) {
        inspection(0, j, n - 1, j);
    }
 
    cout << cnt;
}