[Algorithm]Baekjoon 17069번 :: 파이프 옮기기 2

https://www.acmicpc.net/problem/17069

17069번: 파이프 옮기기 2

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n;
int arr[32][32] = { 0 };
long long dp[32][32][3] = { 0 };
int dirs[3][2] = { {0,1}, {1,1}, {1,0} }; // 가로 대각선 세로
 
bool isValid(int y, int x, int dir)
{
    int nextY = y + dirs[dir][0];
    int nextX = x + dirs[dir][1];
 
    if (nextY < 0 || nextY == n) return false;
    if (nextX < 0 || nextX == n) return false;
    if (arr[nextY][nextX] == 1) return false;
 
    return true;
}
 
long long DFS(int y, int x, int dir)
{
    if (y == n - 1 && x == n - 1) return 1;
    if (dp[y][x][dir] != -1) return dp[y][x][dir];
 
    long long result = 0;
 
    bool isValidRight = isValid(y, x, 0);
    bool isValidDiagonal = isValid(y, x, 1);
    bool isValidDown = isValid(y, x, 2);
 
    if (dir == 0) // 가로로 놓여져있는상태면
    {
        if (isValidRight)
        {
            result += DFS(y + dirs[0][0], x + dirs[0][1], 0);
        }
 
        if (isValidRight && isValidDiagonal && isValidDown)
        {
            result += DFS(y + dirs[1][0], x + dirs[1][1], 1);
        }
    }
    else if (dir == 1) // 대각선
    {
        if (isValidRight)
        {
            result += DFS(y + dirs[0][0], x + dirs[0][1], 0);
        }
 
        if (isValidDown)
        {
            result += DFS(y + dirs[2][0], x + dirs[2][1], 2);
        }
 
        if (isValidRight && isValidDiagonal && isValidDown)
        {
            result += DFS(y + dirs[1][0], x + dirs[1][1], 1);
        }
    }
    else // 세로
    {
        if (isValidDown)
        {
            result += DFS(y + dirs[2][0], x + dirs[2][1], 2);
        }
 
        if (isValidRight && isValidDiagonal && isValidDown)
        {
            result += DFS(y + dirs[1][0], x + dirs[1][1], 1);
        }
    }
 
    return dp[y][x][dir] = result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> arr[i][j];
        }
    }
 
    memset(dp, -1, sizeof(dp));
 
    cout << DFS(0, 1, 0);
}

 

0,에서 n-1,n-1까지 이동가능한 경우의 수를 구하는 꽤나 자주나오는 유형의 문제인데, 대각선이동 시 대각선만 검사하는게 아니라 오른쪽과 아래도 검사해야 한다.

즉 대각선,오른쪽,아래가 전부 이동가능해야만 대각선이동을 할 수 있다.

그리고 각 칸마다 들어오는 방향이 다르기 때문에 dp를 3차원으로 해줬다.

좀 스탠다드한 유형이라서 안풀어본 사람들은 풀어보는게 좋을듯하다.

이런 유형은 바텀업코드도 생각하기 쉽고.. 오히려 보통은 바텀업코드를 먼저 생각하기도 한다.

거의 비슷한 느낌이라 생략한다.