백준 17070번 파이프 옮기기 1

🔒[문제 url]

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

🔑알고리즘

현재 지점으로 파이프의 끝이 도달하기 위해서는, 다음 조건중 하나를 만족해야 한다.
1. 왼쪽 지점에 파이프의 끝이 가로 혹은 대각으로 존재하는 경우
이 경우, 현재 지점에 파이프는 가로 방향으로 배치된다.
2. 왼쪽 위 지점에 파이프의 끝이 존재하는 경우
이 경우, 현재 지점에 파이프는 대각 방향으로 배치된다.
3. 위 지점에 파이프의 끝이 세로 혹은 대각으로 존재하는 경우
이 경우, 현재 지점에 파이프는 세로 방향으로 배치된다.

• 각 지점을 순회하며, 위 세 조건 중 만족하는 조건이 있다면
  dp[i][j]에 배치되는 방향을 표기한다.
  이때, 파이프를 옮길 때 빈 칸이어야 하는 곳이 0인지 확인해야함에 유의한다.
• 1 : 가로 2 : 세로 3 : 대각으로 표기한다.

🐾부분 코드

void checkL(int x,int y)
{// 왼쪽 지점에 파이프 끝이 가로or대각이면 현재 지점에 가로로 옮겨짐
    if(!dp[x][y-1].empty())
    {
        for(int i = 0; i < dp[x][y - 1].size(); i++)
        {
            if(dp[x][y - 1][i] != 2)
                if(home[x][y] != 1)
                    dp[x][y].push_back(1);
        }
    }
}

<왼쪽 지점 체크 함수>
왼쪽 지점에 파이프의 끝이 가로 혹은 대각으로 놓일 수 있다면,
현재 지점에 가로로 놓일 수 있음을 표기한다.

void checkLU(int x,int y)
{// 왼쪽위 대각 지점에 파이프 끝이 존재하면 현재 지점에 대각으로 옮겨짐
    if(!dp[x - 1][y-1].empty())
    {
        for(int i = 0; i < dp[x - 1][y - 1].size(); i++)
        {
            if(home[x][y] != 1 && home[x][y - 1] != 1
            && home[x - 1][y] != 1)
                dp[x][y].push_back(3);
        }
    }
}

<왼쪽 위 지점 체크 함수>
왼쪽 위 지점에 파이프의 끝이 놓일 수 있다면,
현재 지점에 대각으로 놓일 수 있음을 표기한다.
0이어야하는 지점들에 유의한다.

void checkU(int x,int y)
{// 윗 지점에 파이프 끝이 세로or대각이면 현재 지점에 세로로 옮겨짐
    if(!dp[x - 1][y].empty())
    {
        for(int i = 0; i < dp[x - 1][y].size(); i++)
        {
            if(dp[x - 1][y][i] != 1)
                if(home[x][y] != 1)
                    dp[x][y].push_back(2);
        }
    }
}

<윗 지점 체크 함수>
윗 지점에 파이프의 끝이 세로 혹은 대각으로 놓일 수 있다면,
현재 지점에 세로로 놓일 수 있음을 표기한다.

    // 가장 처음에 파이프는 가로 방향으로 (1,1)(1,2)를 차지한다.
    dp[1][2].push_back(1);

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            checkL(i,j); // 왼쪽
            checkLU(i,j); // 왼쪽 위
            checkU(i,j); // 위
        }
    }

    cout << dp[n][n].size();

<초기화 및 각 지점 순회>
문제 조건에 따라 (1,1)(1,2)에 가로 방향으로 파이프를 배치하고 시작한다.
이후 각 지점을 순회하며 dp를 갱신한다.
최종적으로, dp[n][n] 지점에 표기된 경우의 수의 갯수가 출력 답안이 된다.

🪄전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int,int> pii;
int n;
int home[17][17];
vector<int> dp[17][17]; //원소 : 가로 1, 세로 2, 대각 3

void INPUT()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            cin >> home[i][j];
}

void checkL(int x,int y)
{// 왼쪽 지점에 파이프 끝이 가로or대각이면 현재 지점에 가로로 옮겨짐
    if(!dp[x][y-1].empty())
    {
        for(int i = 0; i < dp[x][y - 1].size(); i++)
        {
            if(dp[x][y - 1][i] != 2)
                if(home[x][y] != 1)
                    dp[x][y].push_back(1);
        }
    }
}

void checkLU(int x,int y)
{// 왼쪽위 대각 지점에 파이프 끝이 존재하면 현재 지점에 대각으로 옮겨짐
    if(!dp[x - 1][y-1].empty())
    {
        for(int i = 0; i < dp[x - 1][y - 1].size(); i++)
        {
            if(home[x][y] != 1 && home[x][y - 1] != 1
            && home[x - 1][y] != 1)
                dp[x][y].push_back(3);
        }
    }
}

void checkU(int x,int y)
{// 윗 지점에 파이프 끝이 세로or대각이면 현재 지점에 세로로 옮겨짐
    if(!dp[x - 1][y].empty())
    {
        for(int i = 0; i < dp[x - 1][y].size(); i++)
        {
            if(dp[x - 1][y][i] != 1)
                if(home[x][y] != 1)
                    dp[x][y].push_back(2);
        }
    }
}

void SOLVE()
{
    // 가장 처음에 파이프는 가로 방향으로 (1,1)(1,2)를 차지한다.
    dp[1][2].push_back(1);

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            checkL(i,j); // 왼쪽
            checkLU(i,j); // 왼쪽 위
            checkU(i,j); // 위
        }
    }

    cout << dp[n][n].size();
}

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

너무 어렵다고 느껴지던 DP도 이제 Gold 하위 문제는 쉽게 풀 수 있어 다행이다!
다만 Gold3만 되면... 쩔쩔매기 시작한다.
AC rating 물Gold1 어쩌면 좋아~~~