[ 백준 17069 ] 파이프 옮기기2(2) (C++)

백준의 파이프옮기기2(17069) 문제의 두 번째 풀이이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 풀이(1) 글에서는 이 문제를 DFS + Dynamic Programming의 방법으로 푸는 풀이를 올렸었다.

  [ DFS + DP풀이 바로가기 ]

  지난 글에서의 풀이를 다시한번 요약하자면, DFS의 재귀적 성질을 이용해서 모든 정점을 탐색하는 완전탐색 방법을 사용하되,

  DP의 개념으로 이미 도착점 까지 갈 수 있는 경로의 수를 알고 있는 정점에 대해서는 더 이상 탐색하지 않고 그 경로의 수를

  받아오게 함으로써 탐색의 시간을 줄이는 방법이었다.

  그렇다면 이번글에서는 DFS의 개념도 빼고 Dynamic Programming의 방법으로만 푸는 방법을 알아보자.

  먼저 코드가 진행되는 전체적인 알고리즘에 대해서 설명하자면, 모든 정점을 2중 for문을 통해 방문을 하게 된다.

  이 때, 현재 정점까지 올 수 있는 경우의수를 모두 구하면서 마지막 좌표(N - 1, N - 1)까지 진행하게 되는 방식이다.

  무슨 말인지 잘 모르더라도 밑에서 더욱 구체적으로 설명하겠으니 그냥 읽어보도록 하자.

  사용된 핵심 변수로는 int DP[][][] 라는 3차원 배열이 있다.

  DP[a][b][c(0 / 1 / 2)] = d 의 의미는 "(a, b)에서 c의방향으로 진행한다고 가정했을 때, (a, b)까지 올 수 있는 경우의수

  는 d개 입니다." 가 된다.

  문제와 같은 방향으로 진행하는 하나의 예를 보면서 구체적으로 알아보자.

 

   이러한 맵이 있다고 생각해보자. 문제와 똑같이 (0, 1)에서 오른쪽 방향을 본 채로 시작한다고 가정하겠다.

   또한, DP[][][C]에서 C의값은 0 or 1 or 2라고 간단하게만 설명했는데, 여기서 값의 의미는

   0 = 동쪽 , 1 = 남쪽 , 2 = 대각선아래 로 향하는 방향이라고 가정하겠다.

   즉, DP[0][1][0] = 1 이되는것이다. (0, 1)에서 오른쪽 방향으로 진행할 때, (0, 1)까지 올 수 있는 경우의 수는 1개이기 때문이다.

   그렇다면, 오른쪽으로 한칸 더 진행했을 떄, (0, 2)에서 오른쪽으로 향할 때 (0, 2)까지 올 수 있는 경우의 수는 몇개일까??

   아마 1가지일 것이다. 왜냐하면 (0, 1)에서 오른쪽으로 한칸 이동해서 오는 경우의 수 밖에 없기 때문이다.

   하지만, 이거는 너무 쉽고 극단적인 예일 뿐이다. 그렇다면 가장 정중앙에 있는 좌표인 (2, 2)에서 오른쪽으로 진행할 때의

   경우의 수를 알아보자. 몇 개일까??

   (0, 2)를 구한것과 같이 생각을 한다면, (2, 1)에서 오른쪽으로 오는 경우만 존재하니, 아마 답이 (2, 1)까지 올 수 있는

   경우의 수를 그대로 가져온다고 생각할 수 있다.

   하지만, (2, 2)에서 오른쪽으로 진행할 때, (2, 2)로 올 수 있는 경우는 2가지가 있다.

   바로 (2, 1)에서 오른쪽으로 진행하는 경우와, (1, 1)에서 대각선으로 진행하다가 (2, 2)에서 오른쪽으로 꺽어버리는 경우가 있다.

   즉, 이 모든 경우를 모두 더해줘야 (2, 2)에서의 오른쪽으로 진행한다고 가정했을 때, (2, 2)까지 올 수 있는 경우의 수를

   모두 구할 수 있는 것이다.

   그렇다면, (2, 2)에서 오른쪽이 아닌 아래쪽으로 향한다고 생각하면 어떤 경우가 있을까??

   바로, (1, 1)에서 대각선으로 향하다가 (2, 2)에서 아래쪽으로 방향을 꺽는 경우와 (1, 2)에서 아래쪽으로 쭉 진행하는 경우가

   존재하게 된다.

   마지막으로 (2, 2)에서 대각선으로 향한다고 생각하면??

   (1, 1)에서 대각선으로 진행하는 경우, (2, 1)에서 오른쪽으로 진행하다가 (2, 2)에서 대각선으로 꺽는경우, (1, 2)에서 아래쪽으로

   진행하닥 (2, 2)에서 대각선으로 꺽는 경우 이렇게 총 3가지 경우가 모두 존재한다.

   이 경우만 모두 계산을 해주면 된다. 이런식으로 (N - 1, N - 1) 까지 진행한다면 결국, DP[N-1][N-1][C] 에는 모든 진행방향에

   대한 경로의 수가 저장되어 있을 것이다.

   정리를 한번 해보자.

   1. 현재 좌표에서 오른쪽으로 향하는 경우 ?

     → 이전 좌표에서 대각선으로 내려오다가 오른쪽으로 꺽는 경우 + 이전 좌표에서 오른쪽으로 쭉 진행하는 경우

   2. 현재 좌표에서 아래쪽으로 향하는 경우?

     → 이전 좌표에서 대각선으로 내려오다가 아래쪽으로 꺽는 경우 + 이전 좌표에서 아래쪽으로 쭉 진행하는 경우

   3. 현재 좌표에서 대각선으로 향하는 경우?

     → 이전 좌표에서 대각선으로 쭉 내려오는 경우 + 이전 좌표에서 오른쪽으로 향하다가 꺽는 경우 + 이전 좌표에서

         아래쪽으로 향하다가 꺽는 경우

   위의 결과를 코드로 구현하면 아래와 같다.

for (int i = 0; i < N; i++)      
{
     for (int j = 0; j < N; j++)
     {
         if (i == 0 && j == 0) continue;   // (0 , 0)은 해당사항 없음
         if (MAP[i][j] == 1) continue;    // 1인 좌표는 탐색을 할 수가 없음.

         if (MAP[i][j + 1] == 0) DP[i][j + 1][0] = DP[i][j][2] + DP[i][j][0]; // 오른쪽으로 진행하는 경우
         if (MAP[i + 1][j] == 0) DP[i + 1][j][1] = DP[i][j][2] + DP[i][j][1]; // 아래쪽으로 진행하는 경우
         if (i + 1 < N && j + 1 < N)                // 대각선으로 진행하는 경우
         {
             if (MAP[i + 1][j] == 0 && MAP[i][j + 1] == 0 && MAP[i + 1][j + 1] == 0)

                DP[i + 1][j + 1][2] = DP[i][j][0] + DP[i][j][1] + DP[i][j][2];
          }
     }
}

[ 소스코드 ]

#include<iostream>
 
typedef long long ll;
#define endl "\n"
#define MAX 33
using namespace std;
 
int N;
int MAP[MAX][MAX];
long long DP[MAX][MAX][3]; //3가지 방향에 대해서 동, 남, 대 해당 좌표까지 올 수 있는 경우의 수를 저장
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Solution()
{
    DP[0][1][0] = 1;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (i == 0 && j == 0) continue;
            if (MAP[i][j] == 1) continue;
 
            if (MAP[i][j + 1] == 0) DP[i][j + 1][0] = DP[i][j][2] + DP[i][j][0];
            if (MAP[i + 1][j] == 0) DP[i + 1][j][1] = DP[i][j][2] + DP[i][j][1];
            if (i + 1 < N && j + 1 < N)
            {
                if (MAP[i + 1][j] == 0 && MAP[i][j + 1] == 0 && MAP[i + 1][j + 1] == 0) DP[i + 1][j + 1][2] = DP[i][j][0] + DP[i][j][1] + DP[i][j][2];
            }
            //if (Can_Slash(i, j) == true) DP[i + 1][j + 1][2] = DP[i + 1][j + 1][2] + DP[i][j][0] + DP[i][j][1];
        }
    }
 
    cout << DP[N - 1][N - 1][0] + DP[N - 1][N - 1][1] + DP[N - 1][N - 1][2] << 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;
}