[C++] 백준/Gold/17069. 파이프 옮기기 1/2

파이프 옮기기 문제 정리 및 풀이

문제 개요

• 파이프 옮기기 1: nn의 최대 크기가 16으로, 단순한 탐색 알고리즘으로도 풀이 가능.
• 파이프 옮기기 2: nn의 최대 크기가 32로, 단순 탐색은 시간 초과 발생.

두 문제는 기본적인 로직은 동일하지만, 입력 크기에 따라 효율적인 접근 방식이 필요하다.

 

파이프 옮기기 1 (탐색 방식)

탐색 방식으로 모든 경로를 BFS로 탐색하여 풀이한다.
탐색할 때 파이프의 세 가지 상태(가로, 대각선, 세로)를 기준으로 이동 가능 여부를 판단한다.

코드 설명

1. BFS 탐색
   • queue를 이용해 파이프의 현재 상태를 관리한다.
   • 이동 가능한 위치를 계산하고, 조건을 만족하는 경우 dpdp 배열에 이동 경로를 추가한다.
2. 결과 출력
   • dp[n−1][n−1]dp[n-1][n-1]: 도착점까지의 경로 수 출력.

코드

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<vector<bool>> v(n, vector<bool>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int input; cin >> input;
            v[i][j] = input;
        }
    }
    int offset[3][3][2] = { { {0,1},{1,1},{0,0} },{ {0,1},{1,1},{1,0} },{{0,0},{1,1},{1,0}} };
    vector<vector<int>> dp(n, vector<int>(n));
    queue<tuple<int, int, int>> bfs;
    dp[0][1] = 1;
    bfs.push({ 0, 1, 0});
    while (!bfs.empty()) {
        int x, y, type; tie(y, x, type) = bfs.front();
        bfs.pop();
        for (int i = 0; i < 3; i++) {
            int xx = x + offset[type][i][1];
            int yy = y + offset[type][i][0];
            if (xx == x && yy == y) continue;
            if (xx < 0 || xx >= n || yy < 0 || yy >= n || v[yy][xx]) continue;
            if (i == 1 && (v[yy][xx - 1] || v[yy - 1][xx])) continue;
            dp[yy][xx]++;
            bfs.push({ yy, xx, i });
        }
    }
    cout << dp[n - 1][n - 1];
}

 

파이프 옮기기 2 (DP 방식)

nn이 커지면 탐색 방식으로는 시간 초과가 발생하므로 동적 계획법(DP)을 사용한다.
파이프의 세 가지 상태를 각각 배열로 관리하며, 가능한 이동 경로를 누적 계산한다.

코드 설명

1. DP 배열 초기화
   • dp[0][i]dp[0][i]: 첫 번째 행에 가로로 놓인 경우 초기화.
2. DP 점화식
   • dp[0][i][j]dp[0][i][j]: 가로 상태로 이동 가능하면 이전 가로, 대각선 경로를 누적.
   • dp[1][i][j]dp[1][i][j]: 대각선 상태는 이전 세 방향에서 모두 가능.
   • dp[2][i][j]dp[2][i][j]: 세로 상태로 이동 가능하면 이전 세로, 대각선 경로를 누적.
3. 결과 출력
   • dp[0][n−1][n−1]+dp[1][n−1][n−1]+dp[2][n−1][n−1]dp[0][n-1][n-1] + dp[1][n-1][n-1] + dp[2][n-1][n-1]: 도착점까지의 경로 수 출력.

코드

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

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    vector<vector<int>> v(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> v[i][j];
        }
    }
    vector<vector<vector<long long>>> dp(3, vector<vector<long long>>(n, vector<long long>(n)));
    for (int i = 1; i < n; i++) {
        if (v[0][i]) break;
        dp[0][0][i] = 1;
    }
    for (int i = 1; i < n; i++) {
        for (int j = 2; j < n; j++) {
            if (v[i][j]) continue;
            dp[0][i][j] += dp[0][i][j - 1] + dp[1][i][j - 1];
            if (!v[i - 1][j] && !v[i][j - 1]) 
                dp[1][i][j] += dp[0][i - 1][j - 1] + dp[1][i - 1][j - 1] + dp[2][i - 1][j - 1];
            dp[2][i][j] += dp[1][i - 1][j] + dp[2][i - 1][j];
        }
    }
    cout << dp[0][n - 1][n - 1] + dp[1][n - 1][n - 1] + dp[2][n - 1][n - 1];
}