[ 백준 14890 ] 경사로 (C++) - 구현

---

🔗 문제 링크

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

14890번: 경사로

---

💡 문제 풀이 및 해석

1. 한칸씩 이동하는 문제이다. 이동하는 케이스는 총 3가지이다.
   Case 1 : 평지 이동, Case 2 : 위로 이동, Case 3 : 아래로 이동
2. Case 1 : 연속해서 평지를 이동할 때마다 연속으로 이동한 칸 수(Stack)를 더해준다.
3. Case 2 : 위로 이동하는 것은 (연속으로 이동한 칸 수 >= L) 이어야 가능하다. 위로 이동한 칸은 경사로를 설치할 수 있으므로 Stack=1로 초기화시키고 위로 이동한다.
4. Case 3 : 아래로 이동하는 것은 앞으로 L칸만큼 검사한 뒤에 설치할 수 있으면 설치하고 L칸 뒤로 이동한다. 단, L칸 뒤에는 아래로 내려가는 경사로가 설치되어 있는 상태이므로 Stack=0이 된다.
5. 위의 케이스들을 만들어주고, 가로와 세로를 모두 검사하면 된다.
   더 자세한 설명은 주석으로 달아두었다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#define endl "\n"

using namespace std;

int N, L;
int MAP[101][101];
void init() {
    cin >> N >> L;
    for (int y = 1; y <= N; y++) {
        for (int x = 1; x <= N; x++) {
            cin >> MAP[y][x];
        }
    }
}

bool searchRow(int x, int y, int Stack) {
    if (x == N) {
        return true;
    }
    else {
        int diff = MAP[y][x + 1] - MAP[y][x];
        if (abs(diff) > 1) return false;
        else if (diff == 0) {
            return searchRow(x + 1, y, Stack + 1);
        }
        else if (diff > 0) { // 올라가는 길
            if (Stack >= L) {
                return searchRow(x + 1, y, 1);
            }
            else return false;
        }
        else if (diff < 0) { // 내려가는 길
            if (x + L > N) return false; // 내려갈 만한 칸 자체가 없다면
            for (int i = 1; i <= L; i++) {
                if (MAP[y][x + i] != MAP[y][x] - 1) return false;
            }
            return searchRow(x + L, y, 0);
        }
    }
}

bool searchCol(int x, int y, int Stack) {
    if (y == N) {
        return true;
    }
    else {
        int diff = MAP[y + 1][x] - MAP[y][x];
        if (abs(diff) > 1) return false;
        else if (diff == 0) {
            return searchCol(x, y + 1, Stack + 1);
        }
        else if (diff > 0) { // 올라가는 길
            if (Stack >= L) {
                return searchCol(x, y + 1, 1);
            }
            else return false;
        }
        else if (diff < 0) { // 내려가는 길
            if (y + L > N) return false; // 내려갈 만한 칸 자체가 없다면
            for (int i = 1; i <= L; i++) {
                if (MAP[y + i][x] != MAP[y][x] - 1) return false;
            }
            return searchCol(x, y + L, 0);
        }
    }
}

void sol() {
    int answer = 0;
    for (int y = 1; y <= N; y++) {
        if (searchRow(1, y, 1)) answer++;
    }
    for (int x = 1; x <= N; x++) {
        if (searchCol(x, 1, 1)) answer++;
    }
    cout << answer;
}

int main() {
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

    init();
    sol();

    return 0;
}

---

🤔 문제 후기

처음에는 문제를 푸는 것을 실패하고, 몇일 후에 푼 것인데, 생각보다 쉽게 풀렸다... 처음에는 내려가는 길도 1칸씩 이동하다 보니 그곳에서 실수가 있었던 것 같다. 이번에 풀 때, 생각해보니 위에서 푸는 방식의 풀이 방법이 문득 생각나서 풀었는데, 바로 해결 되었다. 구현 문제는 아이디어만 떠오르면 문제 난이도가 크게 상관 없다고 다시 한번 더 생각하게 된 문제다.