문제 : boj 14890

풀이

  • 가로방향 이동을 하고, 그것을 세로방향으로 똑같이 해주면 된다.
  • 왼쪽에서 오른쪽 방향으로, 위에서 아래 방향으로 움직이면서 이동이 가능한 길인지 판단한다.
  • cnt : 경사로를 설치해 끝까지 이동이 가능한 길의 수(canpass가 true면 cnt가 하나 증가하고, 경사로 설치가 불가능하다고 판단되면 canpass = false가 되어 숫자를 세지 않는다.)
  • 경사로의 길이가 L이상이어야 하므로 이전까지의 길이를 l에 저장해 비교한다.
  • down : l이라는 하나의 변수에 값을 저장해 사용하게되면 높이가 높아지는 경우에는 바로 판단이 가능하지만 높이가 낮아지는 경우에는 낮아지고 난 이후의 길이를 l에 저장해야 한다. down이라는 변수를 통해서 down이 true이면 다음에 높이가 변할 때, 이전의 상황을 반영해 판단하게 된다.
  • (1)위치는 l이 L보다 크므로 경사로를 설치할 수 있다. (3)위치는 경사로를 두개 설치해야 하므로 l이 2*L보다 길어야 하지만 짧으므로 경사로 설치가 불가능하고 따라서 이경우는 canpass가 false가 되고, break를 통해 for문에서 빠져나간다.

C++

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

int N, L, map[101][101];

int findpassway(){
    int cnt(0), l(1); bool canpass=true, down=false;
    // 가로방향 이동
    for(int n(0); n < N; n++){
        l=1; down=false; canpass=true;
        for(int m(1); m < N; m++){
            if (abs(map[n][m] - map[n][m-1]) > 1){
                canpass = false;
                break;
            }
            if(map[n][m] > map[n][m-1]){
                if(l < L) {
                    canpass = false;
                    break;
                }
                if(down){
                    if(l < 2*L) {
                        canpass = false;
                        break;
                    }
                    else down=false;
                }
                l = 1;
            }
            else if(map[n][m] < map[n][m-1]){
                if(down){
                    if(l < L){
                        canpass=false;
                        break;
                    }
                }
                if(m > N-L){
                    canpass = false;
                    break;
                }
                l = 1; down=true;
            }
            else if(map[n][m] == map[n][m-1]) l++;
        }
        if(canpass) cnt++;
    }

    // 세로방향 이동
    for(int n(0); n < N; n++){
        l=1; down=false; canpass=true;
        for(int m(1); m < N; m++){
            if (abs(map[m][n] - map[m-1][n]) > 1){
                canpass = false;
                break;
            }
            if(map[m][n] > map[m-1][n]){
                if(l < L) {
                    canpass = false;
                    break;
                }
                if(down){
                    if(l < 2*L) {
                        canpass = false;
                        break;
                    }
                    else down=false;
                }
                l = 1;
            }
            else if(map[m][n] < map[m-1][n]){
                if(down){
                    if(l < L){
                        canpass=false;
                        break;
                    }
                }
                if(m > N-L){
                    canpass = false;
                    break;
                }
                l = 1; down=true;
            }
            else if(map[m][n] == map[m-1][n]) l++;
        }
        if(canpass) cnt++;
    }

    return cnt;
}

int main(){
    freopen("input.txt", "r", stdin);
    cin >> N >> L;
    for(int n(0); n < N; n++){
        for(int m(0); m < N; m++){
            cin >> map[n][m];
        }
    }

    cout << findpassway();

    fclose(stdin);

    return 0;
}