파이프 옮기기 1 - 17070번 백준

문제

문제 난이도 : 골드 5

문제 분류: 다이나믹 프로그래밍

문제 리뷰

• 경로 문제 -> DP 가능한지 살펴보기
• 백준에서 memset 쓸 때는 memory.h 포함하기
• 그래도.. BFS / DFS + 구현은 빠르게 할 수 있게 된듯
• BFS -> DFS 바꿀 때 vector로 바꾸고 pop_back(), push_back()으로만 바꾸면 되는듯?

문제 풀이

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_set>
#include <memory.h>
using namespace std;

void Init()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int main()
{
    //Initialize
    Init();
    int n;
    int Count = 0;
    cin >> n;
    bool Map[30][30];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            bool tmp;
            cin >> tmp;
            Map[i][j] = tmp;
        }
    }
    int Cache[3][30][30];
    memset(Cache, 0, 2700 * sizeof(int));
    // 0 == 가로 | 1 == 세로 | 2 == 대각선
    Cache[0][0][1] = 1;
    for (int i = 2; i < n; i++)
    {
        if (Map[0][i] != true)
        {
            Cache[0][0][i] = Cache[0][0][i - 1];
        }
    }
    for (int i = 1; i < n; ++i)
    {
        for (int j = 1; j < n; ++j)
        {
            if (Map[i][j] != true && Map[i - 1][j] != true && Map[i][j - 1] != true)
            {
                Cache[2][i][j] = Cache[0][i - 1][j - 1] + Cache[1][i - 1][j - 1] + Cache[2][i - 1][j - 1];
            }

            if (Map[i][j] != true)
            {
                //가로
                Cache[0][i][j] = Cache[0][i][j - 1] + Cache[2][i][j - 1];
                //세로
                Cache[1][i][j] = Cache[2][i - 1][j] + Cache[1][i - 1][j];
            }

        }
    }
    
    std::cout << Cache[0][n-1][n-1] + Cache[1][n-1][n-1] + Cache[2][n-1][n-1];
    

    //Input
    
}