[백준 10164번] 격자상의 경로

문제 링크

문제

(그림이 있어서 캡쳐본으로 올렸다.)

생각해보기

이 문제를 어떻게 접근할 것인가?

점화식 구하기

처음에는 당황했지만, 차분히 생각해보니 단순한 길 찾기 문제와 다를 게 없다. 왜냐하면 우리는 오른쪽 또는 아래로 움직이는 경우밖에 없기 때문. 고로 이 문제는 다익스트라나 플로이드 알고리즘이 아닌 다이나믹 프로그래밍으로 푸는 문제다.

수학문제에서 경로를 구하는 문제가 기억이 났다. (1,1)에서 출발한다고 할 때, (x,1) , (1,y) 좌표로 가는 모든 경로는 1이고, 나머지 (x,y) = (x-1,y) + (x,y-1) 인 것을 배웠다.(x,y>=2)

고로, 우리의 점화식은

DP[Y][X] = DP[Y-1][X] + DP[Y][X-1] ( X, Y > 2 )

가 된다.

경유하는 방법 구하기

경유해서 길을 찾는 방법은 여러가지가 있을 텐데, 나는 이러한 방법을 사용했다.

0가 그려져 있는 경로를 경유해서 가는 방법은

(1에서 0까지 경로) * (0에서 (N,M)까지의 경로)
그렇다면 1에서 0까지 경로는 구하기 쉬운데, 0에서 (N,M)까지의 경로는 어떻게 구할 것인가?

나는 0의 좌표를 (1,1)로 끌어와서 구하는 방법을 사용했다. 그림처럼 8을 왼쪽 위로 끌고오게 되면 15까지의 거리는 1에서 8까지의 거리와 같기 때문이다

예외 처리

그래서 결국 2차원 배열로 좌표를 다루게 되면, x좌표를 1부터 M까지로 계속 초기화를 시켜줘야 하는데, 이것은 한 가지 식으로만 표현이 불가능해서, K % M == 0 일 때 예외 처리를 해줘야한다. 이 것은 코드를 분석해보면 알 수 있다.

코드

#include <iostream>
#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

int main(){
    int N, M, K;
    cin >> N >> M >> K;
    long long int dp[N+1][M+1];// 1번부터 N*M번 까지.

    for (int i = 0; i<=N; i++)
        for(int j = 0; j<=M; j++)
            dp[i][j] = 0;

    for(int i = 1; i<=M; i++)
        dp[1][i] = 1 ;
    for (int i = 1; i<=N; i++)
        dp[i][1] = 1;


    for(int i = 1; i<N*M; i++){
        int y = i/M + 1;    // 행 구하기
        dp[y][i % M + 1] = dp[y][i%M] + dp[y-1][i%M+1];
    }

    if(K!=0) {
        if(N==1 || M == 1){
            dp[N][M] = 1;
        }
        else {
            int judgeX;
            int judgeY;

            if(K % M == 0) {
                judgeX = M;
                judgeY = K / M;
            }
            else {
                judgeX = K % M;
                judgeY = K / M + 1;
            }

            int newX = M - judgeX + 1;
            int newY = N - judgeY + 1;
            dp[N][M] = dp[judgeY][judgeX] * dp[newY][newX];
        }
    }
    cout << dp[N][M];
}

어렵지 않지만 예외처리가 많았던 문제. 아마 나보다 깔끔하게 풀 수 있는 방법은 얼마든지 있을 것이다.