10164. 격자상의 경로

문제링크 : https://www.acmicpc.net/problem/10164

< 입력 >

N(세로 사이즈, <=15)

M(가로 사이즈, <=15)

K(경유점, 1개일 경우 번호/0개일 경우 0)

< 출력 >

1번에서 K번을 거쳐 M*N번까지 갈 수 있는 최단경로의 수

< 풀이 >

우선 경로의 수는 int 범위 안에서 수행 가능하지만 "15 * 15밖에 안되네 그냥 int로 하자"라고 생각하면 안된다.

나중에 해보면 알겠지만 입력으로 "15 15 0"이 들어올 경우가 최다 경로인데 40,116,600개가 나온다.

18 * 18이상은 int 범위가 넘어가게 된다.

[ 사이즈만 보고 방심하면 히든 케이스에서 터져버린다. 다른 문제 풀 때도 주의해야할 점 ]

이제 풀이로 들어가보면 아이디어 자체는 간단하다. 중학교 때 수학에서 배운 방법을 사용하는 것이다.

이 맵에서 1번부터 8번을 거쳐 15번까지 가는 최단경로의 수는 (1번부터 8번까지 가는 최단경로의 수) * (8번부터 15번까지 가는 최단경로의 수)이다.

위와 같이 시작점을 기준으로 가로/세로, 경유점을 기준으로 가로/세로의 값을 1로 초기화 시킨다.

다음으로 초기화되지 않은 점의 값을 왼쪽과 위의 값의 합으로 한다.

이렇게 진행하고 나면 위와 같은 그림이 만들어진다.

경유점의 값 3은 시작점에서 경유점까지의 최단경로 수,

도착점의 값 3은 경유점에서 도착점까지의 최단경로 수를 나타낸다.

최종적으로 시작점에서 경유점을 거친 도착점까지의 최단경로 수는 3 * 3 = 9가 된다.

+ 경유점이 0개일 경우는 예외로 처리하여 전체에 대해 같은 과정을 수행해준다.

---

- 소스 코드 -

#include<iostream>
/*
 * 중학교 때 수학 시간에 배운 길찾기 방법을 사용했습니다.
 * 점1에서 점2까지의 최단경로의 수를 구하기 위해서
 * 점1의 오른쪽, 아래의 모든 점을 1로 초기화하고
 * 초기화되지 않은 점들 중 가장 왼쪽 위부터 시작해서
 * 자신의 오른쪽 위의 값과의 합을 오른쪽에 씁니다.
 * 즉, dp[i-1][j]+dp[i][j-1]=dp[i][j]가 됩니다.
 * 중단점이 없을 경우와 있을 경우를 구분해서 사용합니다.
 */
using namespace std;
 
int main(void){
    int dp[20][20]={0};
    int m,n,o;
    cin>>n>>m>>o;
    // 입력
    if(o!=0){
        int oI=(o-1)/m;
        int oJ=(o-1)%m;
        int path1=0;
        int path2=0;
        // ㅇ 까지의 경로(path1), ㅇ 이후의 경로(path2)
        for(int i=0;i<=oI;i++){
            dp[i][0]=1;
        }
        for(int j=0;j<=oJ;j++){
            dp[0][j]=1;
        }
        for(int i=oI+1;i<n;i++){
            dp[i][oJ]=1;
        }
        for(int j=oJ+1;j<m;j++){
            dp[oI][j]=1;
        }
        // 시작점의 가로(오른쪽) 세로(아래), ㅇ 의 가로(오른쪽) 세로(아래)를 1로 초기화한다.
        for(int i=1;i<=oI;i++){
            for(int j=1;j<=oJ;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        path1=dp[oI][oJ];
        // 시작점에서 ㅇ 까지의 1로 초기화 되어있지 않은 구간을 통해 dp를 구한다.
        for(int i=oI+1;i<n;i++){
            for(int j=oJ+1;j<m;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        path2=dp[n-1][m-1];
        // ㅇ 에서 끝점까지의 초기화 되어있지 않은 구간을 통해 dp를 구한다.
        
        cout<<path1*path2<<endl;
    }else{
        for(int i=0;i<n;i++){
            dp[i][0]=1;
        }
        for(int j=0;j<m;j++){
            dp[0][j]=1;
        }
        // 시작점의 가로(오른쪽) 세로(아래)를 1로 초기화한다.
        for(int i=1;i<n;i++){
            for(int j=1;j<m;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cout<<dp[i][j]<<" ";
            }
            cout<<endl;
        }
        // ㅇ 가 존재하지 않으므로 시작점부터 끝점까지의 초기화되지 않은 구간을 통해 dp를 구한다.
        cout<<dp[n-1][m-1]<<endl;
    }
}

---