17070번 파이프 옮기기 1

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

2가지 풀이 방법이 있다.

1. BFS(약간 브루트 포스 형식)

2. 다이나믹 프로그래밍

문제를 잘 읽자.

색칠한 칸은 갈 수 없기 때문에

Map[y+1][x] != 1 또는 input[y+1][x] != 1 등등 이런 조건도 써줘야 한다.

다이나믹 프로그래밍으로 풀 때

위의 조건을 깜빡 잊고

왜 안 되는지 고민했었다.(30, 38, 46번 째 줄)

BFS 정답 코드

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
queue<pair<int, pair<int, int> > > q;
 
int Map[20][20] = { 0, };
int N = 0;
 
void one(int y, int x) // 1 = ─
{
    ++x;
 
    if (y <= N && x <= N && Map[y][x] != 1) q.push({ 1,{ y, x } });
}
 
void two(int y, int x) // 2 = 역 /
{
    ++y; ++x;
 
    if (y <= N && x <= N && Map[y][x] != 1 && Map[y - 1][x] != 1 && Map[y][x - 1] != 1) q.push({ 2,{ y, x } });
}
 
void three(int y, int x) // 3 = │
{
    ++y;
 
    if (y <= N && x <= N && Map[y][x] != 1) q.push({ 3,{ y, x } });
}
 
int BFS()
{
    int ret = 0;
 
    // 끝 점 기준
    q.push({ 1,{1, 2} });
 
    while (!q.empty())
    {
        int qSize = q.size();
 
        while (qSize--)
        {
            int now = q.front().first;
            int y = q.front().second.first;
            int x = q.front().second.second;
 
            q.pop();
 
            if (y == N && x == N) ++ret;
 
            if (now == 1) // ─
            {
                one(y, x); two(y, x);
            }
            else if (now == 2) // 역 /
            {
                one(y, x); two(y, x); three(y, x);
            }
            else if (now == 3) // │
            {
                two(y, x); three(y, x);
            }
        }
    }
 
    return ret;
}
 
int main(void)
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) scanf("%d", &Map[i][j]);
 
    printf("%d\n", BFS());
 
    return 0;
}

다이나믹 프로그래밍 정답 코드

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
// pipe[행y][열x][파이프 번호]
// 0 : ㅡ
// 1 : 역 /
// 2 : ㅣ
 
long long pipe[40][40][3] = { 0, };
int input[40][40] = { 0, };
 
int N = 0;
 
void zero(int y, int x, int s)
{
    if (x + 1 <= N && input[y][x + 1] != 1) 
    {
        pipe[y][x + 1][0] += pipe[y][x][s];
    }
}
 
void one(int y, int x, int s)
{
    if (y + 1 <= N && x + 1 <= N && input[y + 1][x] != 1 && input[y][x + 1] != 1 && input[y + 1][x + 1] != 1)
    {
        pipe[y + 1][x + 1][1] += pipe[y][x][s];
    }
}
 
void two(int y, int x, int s)
{
    if (y + 1 <= N && input[y + 1][x] != 1)
    {
        pipe[y + 1][x][2] += pipe[y][x][s];
    }
}
 
int main(void)
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) scanf("%d", &input[i][j]);
 
    pipe[1][2][0] = 1;
 
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (input[i][j]) continue;
 
            if (pipe[i][j][0] != 0)
            {
                zero(i, j, 0); one(i, j, 0);
            }
 
            if (pipe[i][j][1] != 0)
            {
                zero(i, j, 1); one(i, j, 1); two(i, j, 1);
            }
 
            if (pipe[i][j][2] != 0)
            {
                one(i, j, 2); two(i, j, 2);
            }
        }
    }
 
    printf("%lld\n", pipe[N][N][0] + pipe[N][N][1] + pipe[N][N][2]);
 
    return 0;
}