백준 파이프 옮기기 2

 

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

문제와 채점은 위 사이트에서 확인 하실 수 있습니다

 

이 문제는 초기에 1,2에있는 파이프를 이리저리 옮겨 끝좌표 까지 갈수있는 경우의 수를 구하는 문제입니다.

각각 가로 세로 대각선일때 이동가능한 방향과 조건들이 주어져있습니다. 파이프 옮기기 1같은경우는 bfs나 dfs로도 해결이 가능하였을걸로 아는데 옮기기 2는 N의 크기가 커져서 dp를 사용하여 풀어야 합니다.

 

dp배열은 우선 좌표정보와 좌표에서 상태를 저장해야하므로 3차원으로 잡고 상태 같은 경우는 0,1,2 순으로 가로,세로,대각선으로 정했습니다.

 

dp식은 크게 어려울것이 없습니다. 현재 좌표가 i,j라하면

 

dp[i+1][j][0] = dp[i][j+1][0] = dp[i][j][0]+dp[i][j][2]; //다음 상태가 가로인 경우

 

dp[i+1][j][1] = dp[i][j][1]+dp[i][j][2]; //다음 상태가 세로인 경우

 

dp[i+1][j+1][2] = dp[i][j][0]+dp[i][j][1]+dp[i][j][2]; //다음상태가 대각선인 경우

벽이 있을때 이동 불가이므로 각각의 경우 벽 여부만 검사해주면 끝입니다.

 

다음은 코드입니다.

 

#include <iostream>

using namespace std;

int maze[36][36];
long long dp[36][36][3]; //0가로 1세로 2대각

int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL);

    int N; cin >> N;

    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++)
            cin >> maze[i][j];

    dp[1][2][0] = 1;
    for(int i = 1; i <= N; i++)
        for(int j = 2; j <= N; j++) {
           if(maze[i][j+1] != 1)
                dp[i][j+1][0] = dp[i][j][0]+dp[i][j][2];
           if(maze[i+1][j] != 1)
                dp[i+1][j][1] = dp[i][j][1]+dp[i][j][2];

           if(maze[i+1][j+1] != 1 && maze[i][j+1] != 1 && maze[i+1][j] != 1) {
                dp[i+1][j+1][2] = dp[i][j][0]+dp[i][j][1]+dp[i][j][2];
           }
        }
    long long ans = 0;
    for(int i = 0; i < 3; i++) {
        ans += dp[N][N][i];
    }
    cout<<ans;
    return 0;
}