백준 17070번 파이프 옮기기1 (JAVA)

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

17070번: 파이프 옮기기 1

 

저는 해당 문제를 DP를 적용하여 문제를 해결하였습니다. dp[y][x][현재 방향]에 대한 경로 값을 저장하였습니다.

마지막으로 대각선 방향일 때는 (y,x-1) , (y-1,x)가 0인지를 확인하였습니다.

package BOJ.DP;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.function.Function;

public class BOJ_17070 {
    static  int n;
    static int map[][];
    static int dp[][][];
    static int dy[] = {0,1,1};
    static int dx[] = {1,1,0};
    static int dfs(int y , int x,int dir){
//        System.out.printf("%d %d %d \n",y,x,dir);
        if(y == n-1 && x == n-1){
            return 1;
        }
        if(dp[y][x][dir] != -1){
            return dp[y][x][dir];
        }else{
            int result = 0;
            for(int i = -1 ; i <= 1; i++){
                int ndir = dir + i;
                if(ndir >= 0 && ndir <= 2){
                    int ny = y + dy[ndir];
                    int nx = x + dx[ndir];
                    if(ny >= 0 && ny < n && nx >= 0 && nx < n && map[ny][nx] == 0){
                        if(ndir == 1 && (map[ny-1][nx] != 0 || map[ny][nx-1] != 0)){
                            continue;
                        }
                        result += dfs(ny,nx,ndir);
                    }
                }
            }
            dp[y][x][dir] = result;
            return result;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        Function<String,Integer> stoi = Integer::parseInt;
        n = stoi.apply(st.nextToken());
        map = new int[n][n];
        dp = new int[n][n][3];
        for(int i = 0 ; i  < n ; i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j = 0 ; j < n ; j++){
                map[i][j] = stoi.apply(st.nextToken());
                Arrays.fill(dp[i][j],-1);
            }
        }
        System.out.println(dfs(0,1,0));
    }
}