[C/C++] BOJ 14890 :: 경사로

 BOJ 14890 :: 경사로

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

예외 처리 고려를 잘 하지 않고 마구잡이로 코드를 짜다보니 시간이 오래걸렸다 ㅠㅠ

각 예제마다 뭐가 안되는 게 계속 생겨서 그걸 맞게 고치려고 하면 다른 조건이 안되고 ㅠㅠ... 여러 모로 나는 힘들었던 문제...

나의 풀이방법

세로와 가로 한 줄씩 총 2N 번을 탐색하면 되기 때문에 0행과 0열만을 탐색하였다!

내가 처리한 조건으로는

1. 지도의 범위를 벗어날 때, 1) 놓아야하는 경사로를 놓지 못하고 넘어간 경우 break

      2) 그렇지 않은 경우 ans++ 한 후, break 

2. 이웃한 칸의 높이가 2 이상일 때, 경사로를 통해 갈 수 없으므로 break

3. 이웃한 칸의 높이가 1 일 때, 

내리막 길이면, 1) L = 1인 경우, 경사로를 무조건 놓을 수 있기 때문에 경사로를 놓고 앞으로 경사로를 놓을 수 있는 칸을 0으                         로 초기화한다.

     2) L = 1이 아닌경우, 2-1) 경사로를 겹쳐서 놓아야 되면 break

       2-2) 그렇지 않으면, 경사로를 놓아야 한다고 표시하고 경사로를 놓을 수 있는 칸의 수를              증가시킨다.

오르막 길이면, 1) 경사로를 놓을 수 있는 칸이 L 이상인 경우, 경사로를 놓고 경사로를 놓을 수 있는 칸을 1로 초기화한다.

     2) 경사로를 놓을 수 있는 칸이 L 이하인 경우, break

4. 이웃한 칸의 높이가 0일 때,

경사로를 놓을 수 있는 칸을 증가시킨다.

경사로를 놓아야 하는데 놓을 수 있는 칸이 L과 같은 경우,

경사로를 놓고, 경사로를 놓아야한다는 표시를 없애고 경사로를 놓을 수 있는 칸을 0으로 초기화한다.

나의 코드

Github : https://github.com/j2wooooo/Daliy_Algorithms/blob/master/Daliy_Algorithms/BOJ_14890/BOJ_14890.cpp

#include<iostream>
using namespace std;
 
int N, L;
int board[101][101];
int dx[2] = {1,0};
int dy[2] = {0,1};
int ans = 0;
 
void search(int x, int  y, int dir)
{
    int _x = x;
    int _y = y;
    bool flag = true;
    int value = 0;
    int len = 1;
 
    while (1)
    {
        value = board[x][y];
 
        int mx = x + dx[dir];
        int my = y + dy[dir];
        int mvalue = board[mx][my];
 
        if (mx >= N || my >= N) {
            if (flag) ans++;
            break;
        }
        // 차이가 2상이면, break;
        if (abs(value - mvalue) > 1) break;
        // 차이가 1이면, check
        if (abs(value - mvalue) == 1)
        {
            // 내려가는 경사로
            if (value > mvalue) {
                if (L == 1) len = 0;
                else if (!flag) break;
                else {
                    flag = !flag;
                    len = 1;
                }
            }
            // 올라가는 경사로
            else if (mvalue > value)
            {
                if (len >= L) len = 1;
                else break;
            }
        }
        // 차이가 0이면
        else if (value == mvalue)
        {
            len++;
            if (len == L && !flag) {
                flag = !flag;
                len = 0;
            }
        }
        x = mx;
        y = my;
    }
}
 
int main(void)
{
    cin >> N >> L;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> board[i][j];
        }
    }
 
    for (int i = 0; i < N; i++)
    {
        search(0, i, 0);
        search(i, 0, 1);
    }
 
    cout << ans;
 
    return 0;
}