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

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

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 이전 문제인 파이프옮기기1(17070번) 문제와 모든 조건이 똑같은데, 단지 다른조건이 있다면 N의 최대범위가 16이 아닌

   32라는 것이다. 처음에는 파이프옮기기1과 같이 완전탐색 방법으로 구현을 하면 될 것 같다는 생각을 하고 제출해보았지만

   시간초과를 받게 되었다. 시간을 줄이기 위해서 본인은 DFS + Dynamic Programming 개념을 합쳐서 구현해 보았다.

 

2) 여기서 사용되는 DP의 개념과 어떻게 적용되는지 간단하게만 알아보고 가자.

   먼저 DP[][][] 라는 3차원 int형 배열을 하나 선언해주었다. 이 배열의 의미부터 알아보자.

   DP[a][b][c] = d 의 의미는 (a, b)를 c의 진행방향으로 온다면 (N-1, N-1)까지 갈 수 있는 경우의 수가 c개 입니다.

   가 된다. 마지막 'c' 인덱스에는 0, 1, 2 3개의 값중 하나만 들어가게 되어있으며, 본인 코드 기준으로 0은 동쪽, 1은 남쪽, 2 = 대각

   선 진행방향을 의미한다.

   그렇다면 여기서 어떻게 적용되는지 한번 확인해보자.

   가장 먼저, DP[][][]의 모든 인덱스의 초기값은 -1로 설정해 주었다. 즉, DP[][][] 의 값인 -1이라는 것은 아직 경로를 탐색하지

   않은 좌표라는 것을 의미한다. 보다 정확하게 말하자면, 현재 진행방향으로 이 정점에 와본적은 없습니다 라는 것을 의미한다.

   정말 극단적이고 간단한 예를 통해서 구체적으로 알아보자.

 

   파랑칸에서 빨강칸 까지 가야하는 문제에서, 정답을 구해봤더니, 보라색 줄 처럼 가능 경우 1가지와 주황색 줄 처럼 가능 경우 1

   가지, 총 2가지 경우밖에 없는 극단적인 경우가 있다고 생각하자. 또한 진행방향은, 오른쪽 혹은 아래쪽으로 밖에 못간다는 조건

   이 있다고 가정해보자.

   DFS의 재귀를 이용해서 구현할 때, 현재 그 함수내용의 실행조건은 DP[현재x좌표][현재y좌표][진행방향]의 값이 -1일 때만

   실행 가능하다. 즉, -1이 아니라면, DP[현재x좌표][현재y좌표][진행방향]의 값을 그대로 return 해준다.

   무슨 말인지 차근차근 알아보도록 하자.

   먼저 보라색 줄 부터 보자. (진행방향 0 = 동쪽, 1 = 남쪽이라고 전제해 두겠다.)

   보라색 줄은 (0,0)에서 시작하면 진행방향이 오른쪽이다. 현재 DP[0][0][0] = -1이다. 즉, (0, 0)에서 동쪽으로 탐색은 아직

   해보지 않았습니다 를 의미한다. 그렇다면 진행해보자. 진행하는 순간 DP[0][0][0] 의 값을 0으로 바꿔주자. 왜 0으로 바꿔

   주는지는 밑에서 설명하겠다. 일단 바꿔주자.

   (0, 1)의 DP값도 -1이므로 진행, (0, 2)도 진행, 여기서 보라색 줄이 아닌, (0, 3)으로 계속해서 진행했다고 가정해보자.

   물론 이 길로 가면 우리는 도착점인 빨강칸에 도착할 수 없음을 알고 있다. 무튼 진행했다고 가정해보자.

   (0, 3)로 갔다가 (0, 4)로 갔는데, 더 이상 길이 없네? 라는 판단을 내렸다고 치자. 뭐 예를 들어서 장애물이 있었다는 그런 생각으

   로 넘겨짚자. 그렇게 되면, 지금까지 왔던 모든 길의 값들이 0이 되 있을 것이다.

   쉽게 얘기해서 DP[0][0][0], DP[0][1][0], DP[0][2][0], DP[0][3][0], DP[0][4][0] 의 값들이 0이 되 있을 것이다.

   왜???? 왜 0이 되어있을까?? 위에서 밑줄 그은 부분을 보면, 진행하는 순간 DP[][][]의 값이 0이 된다고 했기 때문이다.

   즉, 이것이 의미하는 것은, (0, 0) ~ (0, 4)에서 0의 방향, 즉 동쪽으로 진행하시게 되면 빨강칸 까지 가실 수 있는 경로는 0개입니

   다 를 의미하게된다. 그렇다면 (0, 2)에서 다시 보라색 줄을 따라가보도록 하자.

   보라색줄을 쭉 따라서 가다보니 빨강 칸인 (4, 4)에 도착했다고 생각하자. 우리가 목표하고자 하는 정점에 도달하게 되면

   return 1을 받게되고, 재귀가 순서대로 차근차근 빠지면서, 경로에 있는 모든 좌표의 DP값들이 +1씩 되게 된다.

   즉, (0, 0) (0, 1) (0, 2) ... (2, 2) ... (2, 4) ... (4, 4)가 +1씩 되어 1의 값을 가지게 된다. 물론 각 좌표마다 진행방향은 다를것이다.

   가장 가운데 값인 (2, 2)를 예를 든다면 DP[2][2][0] = 1 이 될 것이다. 이것이 의미하는 것은

   (2, 2)에서 동쪽 방향으로 진행하시게 되면, 빨강칸까지 가실 수 있는 경우의 수는 1가지가 존재합니다 ! 를 의미한다.

   또 다른 예로, (2, 4)를 들어보자면 DP[2][4][1] = 1이 되어 있을 것이고, 이는 (2, 4)에서 남쪽 방향으로 진행하시면 빨강 칸 까지

   가실 수 있는 경우의 수는 1가지가 존재합니다 ! 를 의미하게 된다.

 

   그렇다면 이제 주황색 줄을 한번 진행해보도록 하자. 진행하기 전, 한가지만 더 기억해두자. 저 위에서 함수내용의 실행조건은

   DP[x][y][진행방향] 의 값이 -1 일때만 진행한다고 하였다. 그렇다면, 주황색 길을 따라가다 보면 어느 지점이 -1이 아닌 처음

   정점으로 나타나게 될까? 바로 (2, 2)이다. (2, 2)는 이미 1의 값을 가지고 있다. 즉 -1이 아니기 때문에 (2,2)의 값을 return 받게 된

   다. 이게 무슨 소리일까?? 왜 주황색 길에서는 더이상 탐색하지 않고 (2, 2)의 값은 return 받는 것일까?

   생각을 해보자. (2, 2)에서 동쪽 방향으로 진행하면 빨강 칸으로 갈 수 있는 경우의 수는 1가지가 존재합니다 라는 것을 우리는

   보라색 길을 통해서 이미 알고있고 그 값은 DP[2][2][0] 에 저장해두었다. 그렇다면, 주황색길을 따라서 동쪽으로 움직이다가

   (2, 2)를 만나게 되면, 또 탐색을 할 필요가 있을까? 해보나마나 어차피 경우의수가 1가지 나올텐데, 굳이 더이상 탐색을 할 필요

   가 없다는 것이다.

   그렇다고, 정말 말도안되는 상황이지만, 주황색길을 따라가는데, (2,0)에서 순간이동을 해서 (0, 3)으로 갔다고 생각해보자.

   그렇다면 이 경우에도 함수의 내용을 실행할 수 있을까??? 아니다. (0, 3)도 0이라는 값을 가지고 있다. 즉, (0, 3)에서 현재 진행

   방향으로 진행하신다면 도착점에 갈 수 있는 경로의 수는 0개입니다를 의미한다. 즉, 더 이상 탐색을 해볼 필요가 없이 "아 !

   이 길로 가면 도착점에 갈 수 있는 경우의 수가 0개 이구나 !" 라는 것을 알 수 있는 것이다.

   일단 함수의 내용이 실행되면 DP[][][]의 값을 0으로 일단 바꿔주라는 말을 위에서 했었다. 그 이유가 여기에 있다.

   굳이 -1로 초기화시켜놓은 이유는, 0이라는 것은 도착점까지 갈 수 있는 경로의 수가 0개라는 의미있는 값을 가지는 역할을

   하기 때문이고, 지금 당장은 현재 경로로 탐색을 했을 때 도착점에 도착할 수 있을지 없을지는 모르지만, 도착할 수 없다면

   그대로 0이라는 값을, 도착할 수 있다면 + 1이 되어, 값이 계속해서 쌓이는 그런 결과값을 가지게 되기 때문이다.

   즉, 아직 한번도 가보지 못한 정점을 탐색할 때, 그 순간은

   "이 길로 가면 도착점에 갈 수 있을지 없을지 모르겠어요. 계속 탐색해볼게요." 라는 의미를 가지지만, 탐색을 다 종료하고

   다른 길로 탐색을 할 때 또 이 정점을 만나게 되면 "이 길로 가봤더니 경우의 수가 x개 있어요" 라는 것을 DP[][][]배열을 통해서

   우리는 알 수 있는 것이다.  

  

   위에서 이야기한 내용을 이번 문제에 그대로 적용시키기만 하면 된다. 설명을 잘 이해했다면 코드를 보고 이해하기 쉬울 것이다.

   마지막으로 정리한번 하고 이번 문제의 정답코드를 보도록 하자.

   1. DP[A][B][C]의 역할은, (A, B)에서 C의 방향으로 진행을 했을 때, 도착점까지 갈 수 있는 경로의 수를 저장하는 역할이다.

   2. 이미, 경로를 탐색해본 정점이라면, 즉 DP[][][]의 값이 -1이 아닌 다른 값을 가지고 있다면, 그대로 DP[][][]의 값 return

   3. 도착점에 도착했다면 1을 return.

   여기서 1을 return 해주는 이유는, 해당 루트로 와봤더니, 경우의 수가 한가지가 있네요 ! 를 의미한다.

[ 소스코드 ]

#include<iostream>
#include<queue>
#include<cstring>
 
typedef long long ll;
#define endl "\n"
#define MAX 16
using namespace std;
 
int N;
ll Answer;
int MAP[MAX][MAX];
ll DP[MAX][MAX][3];
queue<pair<pair<int, int>, int>> Q;
 
int dx[] = { 0, 1, 1 };
int dy[] = { 1, 0, 1 };
// 동 남 대
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
    memset(DP, -1, sizeof(DP));
}
 
bool Can_Turn(int x, int y)
{
    if (MAP[x + 1][y] == 0 && MAP[x][y + 1] == 0 && MAP[x + 1][y + 1] == 0) return true;
    return false;
}
 
ll DFS(int x, int y, int Dir)
{
    if (DP[x][y][Dir] != -1) return DP[x][y][Dir];
    if (x == N - 1 && y == N - 1) return 1;
 
    DP[x][y][Dir] = 0;
    if (Dir == 0)
    {
        int nx = x + dx[Dir];
        int ny = y + dy[Dir];
        if (nx >= 0 && ny >= 0 && nx < N && ny < N)
        {
            if (MAP[nx][ny] == 0)
            {
                DP[x][y][Dir] = DP[x][y][Dir] + DFS(nx, ny, Dir);
            }
        }
 
        nx = x + dx[2];
        ny = y + dy[2];
        if (nx >= 0 && ny >= 0 && nx < N && ny < N)
        {
            if (Can_Turn(x, y) == true)
            {
                DP[x][y][Dir] = DP[x][y][Dir] + DFS(nx, ny, 2);
            }
        }
    }
    else if (Dir == 1)
    {
        int nx = x + dx[Dir];
        int ny = y + dy[Dir];
        if (nx >= 0 && ny >= 0 && nx < N &&  ny < N)
        {
            if (MAP[nx][ny] == 0)
            {
                DP[x][y][Dir] = DP[x][y][Dir] + DFS(nx, ny, Dir);
            }
        }
 
        nx = x + dx[2];
        ny = y + dy[2];
        if (nx >= 0 && ny >= 0 && nx < N && ny < N)
        {
            if (Can_Turn(x, y) == true)
            {
                DP[x][y][Dir] = DP[x][y][Dir] + DFS(nx, ny, 2);
            }
        }
    }
    else if (Dir == 2)
    {
        int nx = x + dx[Dir];
        int ny = y + dy[Dir];
        if (nx >= 0 && ny >= 0 && nx < N && ny < N)
        {
            if (Can_Turn(x, y) == true)
            {
                DP[x][y][Dir] = DP[x][y][Dir] + DFS(nx, ny, Dir);
            }
        }
 
        nx = x + dx[0];
        ny = y + dy[0];
        if (nx >= 0 && ny >= 0 && nx < N && ny < N)
        {
            if (MAP[nx][ny] == 0)
            {
                DP[x][y][Dir] = DP[x][y][Dir] + DFS(nx, ny, 0);
            }
        }
 
        nx = x + dx[1];
        ny = y + dy[1];
        if (nx >= 0 && ny >= 0 && nx < N && ny < N)
        {
            if (MAP[nx][ny] == 0)
            {
                DP[x][y][Dir] = DP[x][y][Dir] + DFS(nx, ny, 1);
            }
        }
    }
    return DP[x][y][Dir];
}
 
 
void Solution()
{
    Answer = DFS(0, 1, 0);
    cout << Answer << 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;
}