[백준] 17069 파이프 옮기기2 - 탑다운 DP

문제 링크 : https://www.acmicpc.net/problem/17069

🍊해결방법

• N이 최대 32이므로 최악의 경우 3의 32*32 제곱이 일어나므로 일반 구현으로는 시간초과
• dp를 활용하여 해당 좌표의 경우의 수를 탐색 완료했으며 저장
• 가로, 세로, 대각선일 때 이동하는 방향 다름
• 대각선일 때 특이하게 색칠된 부분이 빈 공간이어야 이동가능!!

😀풀이

import java.io.*;
import java.util.*;

public class Main {

    static int N;
    static int[][] arr;
    // 가로 세로 대각
    static int[] dx = {0, +1, +1};
    static int[] dy = {+1, 0, +1};
    static long[][][] dp;


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 가로 : 가로 대각선
        // 세로 : 아래 대각선
        // 대각선 : 가로 아래, 대각선
        // 1,2 점만 기준으로 현재의 방향이 어느 방향인지에 따라 이동하자

        N = Integer.parseInt(br.readLine());

        arr = new int[N+1][N+1];

        for(int i=1; i<=N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=N; j++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        dp = new long[N+1][N+1][3];

        for(int i=0; i<=N; i++){
            for(int j=0; j<=N; j++){
                Arrays.fill(dp[i][j], -1);
            }
        }

        long ans = pipe(1,2,0);


        System.out.println(ans);

    }


    static long pipe(int x, int y, int dir){

        if (x == N && y == N){
            return 1;
        }

        if (dp[x][y][dir] != -1) return dp[x][y][dir];

        long tmp = 0;

        // 방향에 따라 움직일 수 있는 경우 다르다
        if (dir == 0){
            for(int i=0; i<3; i++){

                if (i == 1) continue;

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

                // 범위안에
                if (range(nx, ny)){
                    // 벽이 아닐 때
                    // 대각선은 특별함
                    if (arr[nx][ny] == 0){

                        if (i==2){
                            if (arr[nx-1][ny] == 0 && arr[nx][ny-1] == 0)
                                tmp += pipe(nx, ny, i);
                        }
                        else{
                            tmp += pipe(nx, ny, i);
                        }

                    }
                }

            }
        }
        else if (dir == 1){

            for(int i=0; i<3; i++){

                if (i == 0) continue;

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

                // 범위안에
                if (range(nx, ny)){
                    // 벽이 아닐 때
                    if (arr[nx][ny] == 0){
                        if (i==2){
                            if (arr[nx-1][ny] == 0 && arr[nx][ny-1] == 0)
                                tmp += pipe(nx, ny, i);
                        }
                        else{
                            tmp += pipe(nx, ny, i);
                        }
                    }
                }

            }

        }
        else{

            for(int i=0; i<3; i++){

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

                // 범위안에
                if (range(nx, ny)){
                    // 벽이 아닐 때
                    if (arr[nx][ny] == 0){
                        if (i==2){
                            if (arr[nx-1][ny] == 0 && arr[nx][ny-1] == 0)
                                tmp += pipe(nx, ny, i);
                        }
                        else{
                            tmp += pipe(nx, ny, i);
                        }
                    }
                }
            }

        }

        dp[x][y][dir] = tmp;

        return dp[x][y][dir];
    }


    static boolean range(int x, int y){

        if (x >= 1 && x <= N && y >= 1 && y <= N)
            return true;
        else
            return false;

    }


}