17069번-파이프 옮기기2

문제

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

17069번: 파이프 옮기기 2

---

접근방법

1) 접근 사고

이 문제는 파이프를 둘 수 있는 경우에 대한 재귀와 각 조건에 대한 칸을 확인해보면서 재귀함수를 진행하면 되는 문제입니다.

2) 시간 복잡도

다이나믹 프로그래밍으로 접근 및 메모리제이션을 활용하여 O(nlogn)

3) 배운 점

DP + 간단한 구현 알고리즘 문제인거 같다.

4) PS

---

정답 코드

#include<bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define pii pair<int,int>
#define mp(X,Y) make_pair(X,Y)
#define mt(X,Y) make_tuple(X,Y)
#define mtt(X,Y,Z) make_tuple(X,Y,Z)
#define ll long long
#define sz(v) (int)(v).size()
 
using namespace std;
 
const int MAX = 33;
int n;
ll cache[MAX][MAX][3];
int moveY[] = {0,1,1};
int moveX[] = {1,1,0};
int board[MAX][MAX];
 
bool isValid(int y, int x, int dir)
{
    if(dir == 0)
    {
        for(int k = 0; k < 1; k++)
        {
            int nextY = y + moveY[k];
            int nextX = x + moveX[k];
            if(!(nextX > 0 && nextX <= n && nextY > 0 && nextY <= n && board[nextY][nextX] == 0))
                return false;
        }
    }
    else if(dir == 1)
    {
        for(int k = 0; k < 3; k++)
        {
            int nextY = y + moveY[k];
            int nextX = x + moveX[k];
            if(!(nextX > 0 && nextX <= n && nextY > 0 && nextY <= n && board[nextY][nextX] == 0))
                return false;
        }
    }
    else if(dir == 2)
    {
        for(int k = 2; k < 3; k++)
        {
            int nextY = y + moveY[k];
            int nextX = x + moveX[k];
            if(!(nextX > 0 && nextX <= n && nextY > 0 && nextY <= n && board[nextY][nextX] == 0))
                return false;
        }
    }
    return true;
}
 
ll search(int y, int x , int dir)
{
    if(x == n && y == n)
    {
        return 1;
    }
 
    ll &result = cache[y][x][dir];
    if(result != -1)
        return result;
    result = 0;
 
    if(dir == 0)
    {
        for(int k = 0; k < 2; k++)
        {
            if(isValid(y, x, k))
                result += search(y + moveY[k], x + moveX[k], k);
        }
    }
    else if(dir == 1)
    {
        for(int k = 0; k < 3; k++)
        {
            if(isValid(y, x, k))
                result += search(y + moveY[k], x + moveX[k], k);
        }
    }
    else if(dir == 2)
    {
        for(int k = 1; k < 3; k++)
        {
            if(isValid(y, x, k))
                result += search(y + moveY[k], x + moveX[k], k);
        }
    }
    return result;
}
 
int main(void)
{
    fastio;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
            cin >> board[i+1][j + 1]; //1 2가 끝점이니 1, 2 부터 시작해야함
    }
 
 
    memset(cache, -1 , sizeof cache);
    cout << search(1, 2, 0) << "\n";
 
}