[ 백준 10164 ] 격자상의 경로 (C++)

백준의 격자상의경로(10164) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) (1, 1)에서 부터 (N, M)까지 오른쪽 혹은 아래쪽으로 인접한 칸으로만 움직이면서 갈 때, 동그라미 친 숫자를 무조건 지나가야

   갈 때의 경우의수를 구하는 문제이다.

   K값(동그라미 친 값) 이 0일 경우에는, 즉, 동그라미가 없는 숫자인 경우에는 그냥 (1, 1) ~ (N, M)까지 갈 수 있는 경우의

   수를 모두 출력해주면된다.

   K값이 있을 경우에는 어떻게 해줘야 할까?? 먼저 (1, 1)에서부터 동그라미가 친 숫자까지 가는 경로의 수와, 동그라미친 숫자 부

   터 (N, M)까지 가는 경우의 수를 곱해주면 된다. 왜 곱해줘야할까 ??

  

   위의 그림에서 A에서 B를 거쳐 C로 갈 수 있는 경우의 수는 총 몇개일까? 6개이다.

   A에서 B로 가는 경우의 수 = 2 , B에서 C로 가는 경우의 수 = 3. 답은 2 x 3 = 6.

  

2) 그렇다면 이제 본격적으로 경우의 수를 구해보자. 본인은 Dynamic Programming 방법을 이용해서 한번 접근해 보았다.

   핵심 변수로는 DP[][] 2차원 배열을 사용하였는데, DP[a][b] = c 의 의미는 (a, b)까지 오는 경로의 수는 c개입니다. 를

   의미한다. 당연하게도 시작점인 (1, 1)의 값은 1이된다. DP[1][1] = 1.

   K값이 0이 아닌 경우에 대해서만 알아보자. 어차피 0인 경우에는 (1, 1)부터 (N-1, M-1)까지 똑같은 방식으로 구현하면 되기

   때문이다.

   K가 아닌 경우에는 먼저(1, 1)에서 동그라미친 숫자까지 가는 경우의 수를 알아야 한다. 이를 위해서, 본인은 입력받을 때

   동그라미 친 숫자가 나오는 좌표를 따로 저장해 두었다.

   먼저, 한 좌표에 도착할 수 있는 방법은 총 2개가 있다. 그 좌표보다 왼쪽에 있는 좌표에서 오른쪽으로 이동해서 오는 경우,

   혹은 그 좌표보다 위쪽에 있는 좌표에서 아래쪽으로 이동해서 오는 경우 이렇게 총 2가지가 있다.

   예를 들어서 (x, y)라는 좌표가 있다고 생각해보자. 그렇다면, (x, y)에 오는 방법은 (x, y - 1)에서 오른쪽으로 이동한 경우,

   (x - 1, y)에서 아래쪽으로 이동한 경우로 총 2가지가 있을 수 있다.

   그렇다면 DP[x][y]의 값은 얼마일까?? 아마 DP[x - 1][y] + DP[x][y - 1] 이 될 것이다.

   왜 ????

   위의 식을 위의 정의의 맞게 풀어서 써보자.

   (x, y)까지 올 수 있는 경로의 수 = (x - 1, y)까지 올 수 있는 경로의 수 + (x, y - 1)까지 올 수 있는 경로의 수 입니다. 가 된다.

   아직도 이해가 안된다면 쉬운 예로 알아보자.

   DP[1][1] = 1이다. 그렇다면 DP[1][2]의 값은 얼마일까?? 당연히 1개일 것이다. (1, 1)에서 오른쪽으로 이동한 경로 한가지 뿐 !

   식으로 써보면 DP[1][2] = DP[1][2] + DP[1][1] + DP[0][2] = 0 + 1 + 0 = 1

   이렇게 DP를 이용해서 동그라미 친 좌표까지의 경로의 수를 먼저 구해보자 ! 아래 코드처럼 !

for (int i = 1; i <= Pos.first; i++)            // Pos.first, Pos.second = 동그라미친 숫자의 x좌표, y좌표
{
     for (int j = 1; j <= Pos.second; j++)
     {
          DP[i][j] = DP[i][j] + DP[i - 1][j] + DP[i][j - 1];
     }
}

    구했다면 이제는 동그라미 친 부분부터 (N, M)까지의 경우의 수를 구해야 한다.

    즉, 동그라미친 좌표가 시작점이 되어버린다는 의미이다. 하지만, DP[동그라미친x좌표][동그라미친y좌표]의 값에는

    아마도 (1, 1)부터 동그라미친 좌표까지 올 수 있는 경우의 수가 저장되어 있을 것이다.

    쉽게 말해서 DP[동그라미x좌표][동그라미y좌표]의 값을 어딘가에 저장해두고 1로 바꿔줘야 한다는 것이다.

    이후, 위의 방식과 똑같이 (N, M)까지의 경로의 수를 구한 후, 어딘가에 저장해둔 동그라미친 부분까지 오는 경로의 수와

    (N, M)까지의 경로의 수를 곱해주면 된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 15 + 1
using namespace std;
 
int N, M, K;
int DP[MAX][MAX];
 
pair<int, int> Pos;
 
void Input()
{
    Pos.first = Pos.second = -1;
 
    cin >> N >> M >> K;
    int Num = 1;
    if (K != 0)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= M; j++)
            {
                if (Num == K)
                {
                    Pos.first = i;
                    Pos.second = j;
                }
                Num++;
            }
        }
    }
}
 
void Solution()
{
    DP[1][1] = 1;
    if (K == 0)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= M; j++)
            {
                DP[i][j] = DP[i][j] + DP[i - 1][j] + DP[i][j - 1];
            }
        }
        cout << DP[N][M] << endl;
    }
    else
    {
        for (int i = 1; i <= Pos.first; i++)
        {
            for (int j = 1; j <= Pos.second; j++)
            {
                DP[i][j] = DP[i][j] + DP[i - 1][j] + DP[i][j - 1];
            }
        }
 
        int Temp = DP[Pos.first][Pos.second];
        DP[Pos.first][Pos.second] = 1;
 
        for (int i = Pos.first; i <= N; i++)
        {
            for (int j = Pos.second; j <= M; j++)
            {
                if (i == Pos.first && j == Pos.second) continue;
                DP[i][j] = DP[i][j] + DP[i - 1][j] + DP[i][j - 1];
            }
        }
        cout << Temp * DP[N][M] << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}