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

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

핵심 아이디어 및 정답 코드

- 파이프를 옮길 수 있는 경우의 수를 구하는 문제

- 접근 방식에 따라 DFS, DP로 풀 수 있음

 

맨 위에부터 DP, DFS(도착지에서 탐색), DFS(출발지에서 탐색)

1. DFS 풀이

https://godgjwnsgur7.tistory.com/47

[Algorithm C#] BFS, DFS ( + Back Tracking )

 

1) 출발지에서 시작

- 직관적으로 주어진 문제에 대하여 완전 탐색을 위한 깊이 우선 탐색 (DFS)을 수행

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

vector<vector<bool>> boolVecs;
int answer;
int maxPos;

void DFS(int posY, int posX, bool dirY, bool dirX)
{
    if (posY >= maxPos || posX >= maxPos || boolVecs[posY][posX])
        return;

    if (dirY && dirX && (boolVecs[posY - 1][posX] || boolVecs[posY][posX - 1]))
        return;

    if (posY == maxPos - 1 && posX == maxPos - 1)
    {
        answer++;
        return;
    }

    if (dirY && dirX)
    {
        DFS(posY + 1, posX, true, false);
        DFS(posY + 1, posX + 1, true, true);
        DFS(posY, posX + 1, false, true);
    }
    else if (dirY)
    {
        DFS(posY + 1, posX, true, false);
        DFS(posY + 1, posX + 1, true, true);
    }
    else // dirX
    {
        DFS(posY + 1, posX + 1, true, true);
        DFS(posY, posX + 1, false, true);
    }
}

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

    answer = 0;
    cin >> maxPos;

    for (int y = 0; y < maxPos; y++)
    {
        int temp;
        vector<bool> boolVec(maxPos);
        for (int x = 0; x < maxPos; x++)
        {
            cin >> temp;
            boolVec[x] = (temp == 1);
        }
        boolVecs.push_back(boolVec);
    }

    DFS(0, 1, false, true);
    cout << answer;
    return 0;
}

 

1) 도착지에서 시작

- 출발지에서 탐색하면, 벽이 없다는 가정 하에도 도착지에 도착할 수 없는 경우의 수도 계산하게 되므로, 필요 없는 연산을 줄일 수 있음

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

bool boolArrays[16][16];
int answer;

void DFS(int posY, int posX, bool dirY, bool dirX)
{
    if (posY < 0 || posX < 0 || boolArrays[posY][posX])
        return;

    if (dirY && dirX && (boolArrays[posY + 1][posX] || boolArrays[posY][posX + 1]))
        return;

    if (posY == 0 && posX == 1)
    {
        if (dirX)
            answer++;
        return;
    }

    if (dirY && dirX)
    {
        DFS(posY - 1, posX, true, false);
        DFS(posY - 1, posX - 1, true, true);
        DFS(posY, posX - 1, false, true);
    }
    else if (dirY)
    {
        DFS(posY - 1, posX, true, false);
        DFS(posY - 1, posX - 1, true, true);
    }
    else // dirX
    {
        DFS(posY - 1, posX - 1, true, true);
        DFS(posY, posX - 1, false, true);
    }
}

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

    answer = 0;
    int maxPos;
    cin >> maxPos;

    for (int y = 0; y < maxPos; y++)
    {
        int temp;
        for (int x = 0; x < maxPos; x++)
        {
            cin >> temp;
            boolArrays[y][x] = (temp == 1);
        }
    }

    if (boolArrays[maxPos - 1][maxPos - 1] == false)
    {
        DFS(maxPos - 1, maxPos - 2, false, true);
        DFS(maxPos - 2, maxPos - 2, true, true);
        DFS(maxPos - 2, maxPos - 1, true, false);
    }
    cout << answer;
    return 0;
}

2. DP 풀이

- DP 알고리즘을 통해 각 좌표에 대하여 도착할 수 있는 경우의 수를 합하여 도착지에 최종적으로 도착할 수 있는 경우의 수를 도출해내는 방법

 

1) 좌표 (y, x) 에 가로 방향으로 도착하는 경우의 수

 -> (y, x - 1) 에 가로 방향으로 도착하는 경우의 수 + 대각선 방향으로 도착하는 경우의 수

 

2) 좌표 (y, x) 에 대각선 방향으로 도착하는 경우의 수

 -> (y - 1, x - 1) 에 대각선 방향으로 도착하는 경우의 수

 

3) 좌표 (y, x) 에 세로 방향으로 도착하는 경우의 수

 -> (y - 1, x) 에 대각선 방향으로 도착하는 경우의 수 + 세로 방향으로 도착하는 경우의 수

 

https://godgjwnsgur7.tistory.com/109

[Algorithm C#] 동적 계획법(DP) / Memoization, Tabulation

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

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

    bool boolArrays[16][16] = { false };
    int dp[16][16][3] = { 0 }; // 0 가로, 1 대각, 2 세로
    int length;
    cin >> length;

    for (int y = 0; y < length; y++)
    {
        int temp;
        for (int x = 0; x < length; x++)
        {
            cin >> temp;
            boolArrays[y][x] = (temp == 1);
        }
    }

    dp[0][1][0] = 1;
    for (int i = 2; i < length; i++)
        if (!boolArrays[0][i])
            dp[0][i][0] = dp[0][i - 1][0];

    for (int y = 1; y < length; y++)
    {
        for (int x = 2; x < length; x++)
        {
            if (!boolArrays[y][x])
            {
                dp[y][x][0] = dp[y][x - 1][0] + dp[y][x - 1][1];
                dp[y][x][2] = dp[y - 1][x][1] + dp[y - 1][x][2];

                if (!boolArrays[y - 1][x] && !boolArrays[y][x - 1])
                    dp[y][x][1] = dp[y - 1][x - 1][0] + dp[y - 1][x - 1][1] + dp[y - 1][x - 1][2];
            }
        }
    }
    
    int answer = dp[length - 1][length - 1][0] + dp[length - 1][length - 1][1] + dp[length - 1][length - 1][2];
    cout << answer;
    return 0;
}