백준 1520번 내리막 길

문제

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

1520번: 내리막 길

풀이

상하좌우로 이동 가능하고 높은 곳에서 낮은 곳으로만 이동이 가능할 때, 왼쪽 위 지점에서 오른쪽 아래 지점까지 이동하는 경우의 수를 구하는 문제입니다. 10164번과 유사하게 점화식을 세울 수 있지만, 위 또는 왼쪽으로도 이동할 수 있다는 점, 그리고 높은 곳에서 낮은 곳으로만 이동 가능하다는 점을 고려해 주어야 합니다.

 

우선 시작 지점을 (1, 1) 그리고 도착 지점을 (N, M)이라고 합시다. (0, 0)과 (N-1, M-1)로 정의하지 않는 이유는 정의된 구역에서 벗어난 지점의 값을 0으로 설정하여 구현을 편하게 하기 위함입니다. 그리고 dp [row][col]을 시작 지점 (1, 1)에서 (row, col)으로 이동하는 경로의 개수라고 정의합니다. 하나의 칸에는 네 방향에서만 들어올 수 있고, 네 방향에서 들어오는 경로 중에 중복되는 것은 없습니다. 따라서 다음과 같이 dp 식을 구할 수 있습니다.

 

dp[row][col] = dp[row-1][col] + dp[row+1][col] + dp[row][col-1] + dp[row][col+1]

 

단, 높은 지점에서 낮은 지점으로만 이동할 수 있다고 했으므로 이 식은 (row, col)이 높이가 가장 낮은 칸인 경우에만 성립합니다. 그러므로 단순히 이중 for문을 이용할 수는 없고, 정렬 과정을 거쳐야 합니다. 높이가 높은 지점이 앞에 오고 낮은 지점이 뒤에 오도록 정렬한 후에 순차적으로 처리하면 지금 처리하고 있는 지점이 가장 낮은 지점이라는 가정을 유지할 수 있습니다. 또한 앞서 나온 지점들은 지금 또는 나중에 나올 지점보다 높이가 높으므로 더 이상의 갱신이 일어나지 않는 상태라는 것을 알 수 있습니다. 다만 이 문제에서는 높이가 같은 지점이 존재할 수 있습니다. 그러나 이것은 값을 계산할 때 높이가 같다면 무시하는 것으로 간단하게 해결할 수 있습니다. 높이가 같은 지점끼리는 서로 영향을 미치지 않으므로 이전에 처리된 값이 변하지 않는다는 사실 또한 유지됩니다.

 

계산을 통해 답을 구하기 위해서는 dp[1][1]의 값을 1로 설정해야 합니다. 그러나 (1, 1)의 높이보다 높은 지점의 dp값을 계산하기 전에 dp[1][1] = 1로 설정해놓으면 현재 처리하고 있는 지점의 높이가 지금까지 처리한 지점들의 높이중 최소라는 가정이 깨지게 됩니다. 이러면 시작 지점 (1, 1)의 값, 즉 자신보다 낮은 지점의 값을 참조하게 되어 잘못된 값을 구하게 됩니다. 따라서 (1, 1)보다 높은 위치를 가진 지점들을 모두 처리한 후, (1, 1)을 처리 할 때 dp[1][1] = 1로 정해 주어야 합니다. 또는 시작 지점보다 높은 지점으로는 절대 지나갈 수 없으므로 그러한 지점들을 모두 건너뛰거나 제거해주어도 됩니다. 이렇게 할 경우에는 초기에 dp[1][1] = 1로 설정해 두어도 문제가 되지 않습니다.

소스 코드

#include <iostream>
#include <tuple>
#include <vector>
#include <algorithm>
using namespace std;

// zero padding이 필요하므로 배열의 크기는 여유롭게 설정
int grid[512][512], dp[512][512];

int main() {
    // 빠른 입출력
    cin.tie(0)->sync_with_stdio(0);
    // row: N col: M 문제의 정의와는 반대이므로 주의
    int N, M;
    cin >> N >> M;
    // (height, row, col) 별도의 구조체와 비교 함수를 만들어도 OK
    vector<tuple<int, int, int>> vec;
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) {
            int& h = grid[i][j];
            cin >> h;
            vec.emplace_back(h, i, j);
        }
    }
    // reverse_iterator을 이용해서 높이가 큰 원소가 앞에 오도록 정렬
    // 대신 greater<>()을 사용해도 OK
    sort(vec.rbegin(), vec.rend());
    const int dr[4] {1, -1, 0, 0};
    const int dc[4] {0, 0, 1, -1};
    // Structured binding
    for (auto [h, i, j] : vec) {
        // 시작지점인 경우 dp값을 1로 설정
        if (i == 1 && j == 1)
            dp[1][1] = 1;
        for (int k = 0; k < 4; k++) {
            int nr = i + dr[k];
            int nc = j + dc[k];
            // 높이가 같은 경우는 무시
            if (grid[nr][nc] == h)
                continue;
            dp[i][j] += dp[nr][nc];
        }
    }
    cout << dp[N][M] << '\n';
    return 0;
}