BOJ 14890 · 경사로

알고리즘 분류 : 시뮬레이션  

경사로를 만들어서 지나갈 수 있는 길의 개수를 구하는 문제다. 문제에 주어진 조건에 따라 그대로 구현해야 한다.

• 지나갈 수 있는 길을 확인하기 위해 가로 방향과 세로 방향을 구분해서 순차 탐색해야 한다.
• 먼저 현재 칸의 높이 A와 다음 칸의 높이 B를 구하고, B-A를 D라고 하자.
• D가 0이라면, 길의 높이가 같은 경우이다.
• D가 1이라면, 올라가는 경사로가 필요한 경우이다.
• D가 -1이라면, 내려가는 경사로가 필요한 경우이다.

• 길의 높이가 같다면 (D == 0), 카운트를 1 증가시킨다. 카운트는 경사로의 길이와 비교하기 위해 필요하다.
• 올라가는 경사로라면 (D == 1), 카운트가 경사로의 길이 L 이상인지 확인한다. 카운트가 L 이상이라면, 경사로를 놓을 수 있는 경우이므로, 카운트를 1로 초기화시킨다.
• 내려가는 경사로라면 (D == -1), 카운트가 0 이상인지 확인한다. 0 이상이라면, 카운트를 경사로의 길이 L만큼을 음수로 만든다. 만약 카운트가 음수라면, 내려가는 경사로를 만들고 있는 중이므로, 경사로를 놓을 수 없다.

---

C++ 소스코드

#include <cstdio>

int N, L, ans;
int a[100][100];

void slope(int i, bool c) {
    int cnt=1;
    for (int j=0; j<N-1; j++) {
        int d = c == 1 ? a[i][j+1]-a[i][j] : a[j+1][i]-a[j][i];
        if (d == 0) cnt++;
        else if (d == 1 && cnt >= L) cnt = 1;
        else if (d == -1 && cnt >= 0) cnt = -L+1;
        else return;
    }
    if (cnt >= 0) ans += 1;
}

void solve() {
    for (int i=0; i<N; i++) {
        slope(i, 1);
        slope(i, 0);
    }
    printf("%d\n", ans);
}

int main() {
    scanf("%d %d", &N, &L);
    for (int i=0; i<N; i++) {
        for (int j=0; j<N; j++) {
            scanf("%d", &a[i][j]);
        }
    }
    solve();
    return 0;
}

---

Python 3 소스코드

def slope(i, c):
    global ans
    cnt = 1
    for j in range(0, N-1):
        d = a[i][j+1]-a[i][j] if c else a[j+1][i]-a[j][i]
        if d == 0:
            cnt += 1
        elif d == 1 and cnt >= L:
            cnt = 1
        elif d == -1 and cnt >= 0:
            cnt = -L+1
        else:
            return
    if cnt >= 0:
        ans += 1

def solve():
    for i in range(N):
        slope(i, 1)
        slope(i, 0)
    print(ans)

N, L = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(N)]
ans = 0
solve()

---

참고

• 백준 온라인 저지 : BOJ 14890