백준[C++] 17070 파이프 옮기기 1

<조건 분석>

1. 방법의 수를 모두 더해라 -> 경우의 수 문제겠다. 라고 생각해봄.

 

2. 파이프가 두 개의 좌표를 물고 있고 대각선일 때는 3개의 좌표를 벽이 있는지 체크함.

 

<구현 생각의 도달>

 

1. 파이프를 옮기는 로직을 생각해내기가 진짜 어려웠음.

 

2. 파이프의 앞선 좌표는 생각할 필요 없음. 이동되는 끝 좌표만 생각하면 됨.

 

3. 그렇게 되면 끝 좌표 따라 벽 체크, 좌표 이동만 해주면 됨.

 

4. 그러면 DFS도 가능함. 결국 DFS도 "모든 경로"를 탐색하면서 목적지까지 도달하게 끔 순회하는 것이므로 모든 경우의 수를 탐색해볼 수 있음. (도시의 수가 적어서 가능한 방법이기도 함)

 

5. DP의 핵심은 부분최적해를 발견하고 그것을 더해나가거나 어떻게 캐싱하느냐의 문제임.

 

6. 여기서 DP의 부분최적해는 해당 위치에서 방향에 따라 다음 경우의 수에 자신의 경우의 수를 더해가는 것임. (솔직히 너무 어려워서 감 잡기가 힘듦.)

 

 

 

<DP 버전>

#include <bits/stdc++.h>
using namespace std;

int n = 0;
int board[17][17];
int dp[17][17][3];

bool check(int x, int y, int dir)
{
    if (dir == 2)
    {
        if (board[x - 1][y] == 0 && board[x][y - 1] == 0 && board[x][y] == 0) return true;
    }
    else 
    {
        if (board[x][y] == 0) return true;
    }

    return false;;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> board[i][j];
        }
    }
    
    dp[1][2][0] = 1; // 처음 시작지점에서의 경우의 수

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            // 가로일 때 다음 경우의 수에 더하기
            if (check(i, j+1, 0)) dp[i][j+1][0] += dp[i][j][0];
            if (check(i+1, j+1, 2)) dp[i+1][j+1][2] += dp[i][j][0];

            // 세로일 때
            if (check(i + 1, j, 1)) dp[i + 1][j][1] += dp[i][j][1];
            if (check(i + 1, j + 1, 2)) dp[i + 1][j + 1][2] += dp[i][j][1];

            // 대각선 일 때
            if (check(i, j+1, 0)) dp[i][j + 1][0] += dp[i][j][2];
            if (check(i + 1, j, 1)) dp[i + 1][j][1] += dp[i][j][2];
            if (check(i + 1, j + 1, 2)) dp[i + 1][j + 1][2] += dp[i][j][2];
        }
    }

    int ret = dp[n][n][0] + dp[n][n][1] + dp[n][n][2];
    cout << ret;

    return 0;
    
}

 

 

<DFS 버전>

#include <bits/stdc++.h>
using namespace std;

int n = 0;
int board[17][17];

int dx[] = {1, 0, 1};
int dy[] = {0, 1, 1};

int ret = 0;

void DFS(int y, int x, int dir) // 0 : 가로 1 : 세로 2 : 대각
{
    if (y == n && x == n) // 수 많은 경로 중 1개의 경우의 수가 목적지 도달 
    {
        ret++;
        return ;
    }

    for (int i = 0; i < 3; i++)
    {
        if (dir == 0 && i == 1) continue;
        if (dir == 1 && i == 0) continue;

        int ny = y + dy[i];
        int nx = x + dx[i];

        if (ny < 0 || nx < 0 || ny > n || nx > n) continue;
        if (board[ny][nx] == 1) continue;

        if (i == 2)
        {
            if (board[ny - 1][nx] == 1 || board[ny][nx - 1] == 1) continue;
        }

        DFS(ny, nx, i);
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            cin >> board[i][j];
        }
    }

    DFS(1, 2, 0);

    cout << ret;

    return 0;
}