[백준] 14890번 경사로

문제

https://www.acmicpc.net/problem/14890

풀이

너무너무 오래 걸린 문제다. 구현 능력을 보는 문제 같은데 예외처리 해야될 게 너무 많아 힘들었다.

행과 열 각각 재귀함수로 검사하는 함수를 만들었다.

함수에는 이전 칸의 높이와 동일한 칸의 수를 넘겼다.

이전 칸과 현재 간 사이의 관계는 세 가지로 정의할 수 있다.

1. 이전 칸보다 현재 칸이 높은 경우
2. 이전 칸보다 현재 칸이 낮은 경우
3. 이전 칸과 현재 칸의 높이가 같은 경우

이전 칸과 현재 칸의 차를 구해서 관계를 구했으며 차가 2이상인 경우는 길로 만들 수 없기 때문에 바로 함수를 종료시켰다.

현재 칸이 높은 경우고 차가 1인 경우는 경사로를 만들어야 되는데 이 때 현재까지 쌓인 cnt값을 이용해서 이전에 존재하는 동일한 칸 수가 L 이상인 경우만 L개의 경사로를 만들어줬다.

현재 칸이 낮은 경우고 차가 1인 경우는 현재 칸부터 앞에 L개의 칸을 경사로로 만들어주는데 현재 칸의 높이와 다른 칸이 발견되면 경사로를 만들 수 없게 되고 이 경우는 길이 될 수 없는 경우이기 때문에 함수를 종료시켰다.

마지막 칸까지 검사가 끝나면 n개의 경사로 배열에서 만들어진 경사로의 개수를 파악해서 길이 될 수 있는지 없는지 판단했다.

소스코드

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAX_SIZE 101

int n, l;
int map[MAX_SIZE][MAX_SIZE];
int runway_row[MAX_SIZE];
int runway_col[MAX_SIZE];
int ans;

// prev_h : 이전 칸의 높이
// x, y : 현재 칸의 x, y 좌표
// cnt : 현재까지 동일한 칸의 개수
void RecurRow(int prev_h, int x, int y, int cnt)
{
    // 행 검사가 끝나면
    if (y == n)
    {
        bool isway = true;
        for (int i = 0; i < n; i++)
        {
            // 경사로의 개수가 두 개 이상이면 길로 만들지 못한다
            if (runway_row[i] > 1)
                isway = false;
        }

        if (isway)
            ans++;

        memset(runway_row, 0, sizeof(runway_row));
        return;
    }

    int abs_sub = abs(map[x][y] - prev_h);

    if (abs_sub == 0)
    {
        RecurRow(map[x][y], x, y + 1, cnt + 1);
    }
    // 차가 1이면
    else if (abs_sub == 1)
    {
        // 현재 칸의 높이가 이전 칸보다 높은 칸이면
        if (prev_h < map[x][y])
        {
            if (cnt >= l)
            {
                for (int i = y - 1, l_cnt = 0; l_cnt < l; i--, l_cnt++)
                {
                    if (i < 0)
                    {
                        memset(runway_row, 0, sizeof(runway_row));
                        return;
                    }
                    // 경사로 개수 추가
                    runway_row[i] += 1;
                }
                RecurRow(map[x][y], x, y + 1, 1);
            }
            else
            {
                memset(runway_row, 0, sizeof(runway_row));
                return;
            }

        }
        // 현재 칸이 더 낮은 칸이면
        else
        {
            // 현재부터 l개의 칸을 경사로로 만들어준다
            for (int i = y, l_cnt = 0; l_cnt < l; i++, l_cnt++)
            {
                if (i >= n)
                {
                    memset(runway_row, 0, sizeof(runway_row));
                    return;
                }
                if (map[x][i] == map[x][y])
                    runway_row[i] += 1;
                // 앞의 l개의 칸 중에서 높이가 다른 칸이 존재하면 경사로를 못만든다
                else
                {
                    memset(runway_row, 0, sizeof(runway_row));
                    return;
                }
            }
            RecurRow(map[x][y], x, y + 1, 1);
        }
    }
    // 차가 1도 아니고 0도 아니면 길이 될 수 없으므로 호출 종료
    else
    {
        memset(runway_row, 0, sizeof(runway_row));
        return;
    }
}

void RecurCol(int prev_h, int x, int y, int cnt)
{
    // 열 검사가 끝나면
    if (x == n)
    {
        bool isway = true;
        for (int i = 0; i < n; i++)
        {
            // 경사로의 개수가 두 개 이상이면 길로 만들지 못한다
            if (runway_col[i] > 1)
                isway = false;
        }
        if (isway)
            ans++;

        memset(runway_col, 0, sizeof(runway_col));
        return;
    }

    int abs_sub = abs(map[x][y] - prev_h);

    if (abs_sub == 0)
    {
        RecurCol(map[x][y], x+1, y, cnt + 1);
    }
    // 차가 1이면
    else if (abs_sub == 1)
    {
        // 현재 칸의 높이가 이전 칸보다 높은 칸이면
        if (prev_h < map[x][y])
        {
            if (cnt >= l)
            {
                for (int i = x - 1, l_cnt = 0; l_cnt < l; i--, l_cnt++)
                {
                    if (i < 0)
                    {
                        memset(runway_col, 0, sizeof(runway_col));
                        return;
                    }
                    // 경사로 개수 추가
                    runway_col[i] += 1;
                }
                RecurCol(map[x][y], x+1, y, 1);
            }
            else
            {
                memset(runway_col, 0, sizeof(runway_col));
                return;
            }
        }
        // 현재 칸이 더 낮은 칸이면
        else
        {
            // 현재부터 l개의 칸을 경사로로 만들어준다
            for (int i = x, l_cnt = 0; l_cnt < l; i++, l_cnt++)
            {
                if (i >= n)
                {
                    memset(runway_col, 0, sizeof(runway_col));
                    return;
                }
                if (map[i][y] == map[x][y])
                    runway_col[i] += 1;
                // 앞의 l개의 칸 중에서 높이가 다른 칸이 존재하면 경사로를 못만든다
                else
                {
                    memset(runway_col, 0, sizeof(runway_col));
                    return;
                }
            }
            RecurCol(map[x][y], x+1, y, 1);
        }
    }
    // 차가 1도 아니고 0도 아니면 길이 될 수 없으므로 호출 종료
    else
    {
        memset(runway_col, 0, sizeof(runway_col));
        return;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> n >> l;

    // #1. 지도 입력
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> map[i][j];
        }
    }

    // #2. 행, 열 검사
    for (int i = 0; i < n; i++)
    {
        RecurRow(map[i][0], i, 0, 0);
        RecurCol(map[0][i], 0, i, 0);
    }

    cout << ans << "\n";

    return 0;
}