[BOJ] 17069. 파이프 옮기기 2

이 문제는 DP로 해결하였다.

맨 처음 문제를 봤을때 재귀적인 그래프의 탐색형태로 접근하려고 했다. 하지만 N의 크기가 재귀를 사용하기에 너무 큰 경우의 수를 가지기에 재귀말고 DP로 접근하게 되었다. 일단 모든 맵의 칸에서 3가지의 경우의수를 가지고 했다. 파이프가 각각 가로,세로,대각선으로 깔리게 되는 3가지로 두었다. 그리고 만일 i,j에서 가로로깔리게 되는 경우의 수를 생각해보면 i-1,j 에서의 가로와 대각선의 경우의 수를 가질수 있게 된다. 이러한 방식으로 다음과 같이 생각하게 되었다.

1) i,j에서 가로의 파이프를 가지는 경우 : (i-1,j에서 가로) + (i-1,j에서 대각선)
2) i,j에서 세로의 파이프를 가지는 경우 : (i,j-1에서 세로) + (i,j-1에서 대각선)
3) i,j에서 대각선의 파이프를 가지는 경우 : (i-1,j-1에서 가로) + (i-1,j-1에서 세로) + (i-1,j-1에서 대각선)
이러한 규칙으로 벽(1) 이 아닐때를 구하게 되었다.

DP를 오랜만에 풀어보느라 점화식을 세움에 있어 어려움이 많았다. 한번더 생각해보는 습관이 필요한 거 같다.

package boj2;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_17069_파이프옮기기2 {
    static int[][] map;
    static long[][][] count;
    
    static int N;
    
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        N=Integer.parseInt(br.readLine());
        map=new int[N][N];
        for(int i=0;i<N;i++) {
            st=new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++) {
                map[i][j]=Integer.parseInt(st.nextToken());
            }
        }
        
        count=new long[N][N][3];
        init();
 
        
        dp();
        
        long answer=0;
        
        
        for(int i=0;i<3;i++)
            answer+=count[N-1][N-1][i];
        System.out.println(answer);
        
    }
    
    static void init() {
        for(int i=1;i<N;i++) {
            if(map[0][i]==0) {
                count[0][i][0]=1;        // 오른쪽방향 1로 셋팅
            }else {
                break;
            }
        }
    }
    
    static void dp() {
        for(int i=1;i<N;i++) {
            for(int j=2;j<N;j++) {
                if(map[i][j]==0) {
                    if(map[i][j-1]==0)
                        count[i][j][0]=count[i][j-1][0]+count[i][j-1][2];
                    if(map[i-1][j]==0)
                        count[i][j][1]=count[i-1][j][1]+count[i-1][j][2];
                    if(map[i-1][j-1]==0 && map[i-1][j]==0 && map[i][j-1]==0)
                        count[i][j][2]=count[i-1][j-1][0]+count[i-1][j-1][1]+count[i-1][j-1][2];
                    
                }
            }
        }
    }
    
    
}
 

 

package algostudy3;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main_bj_17069_파이프옮기기2 {
    static int N;
    static int[][] map;
    static long[][][] dp;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        N = Integer.parseInt(br.readLine());
 
        map = new int[N][N];
        dp = new long[3][N][N];
 
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
                dp[0][i][j] = -1;
                dp[1][i][j] = -1;
                dp[2][i][j] = -1;
            }
        }
 
        System.out.println(dfs(0, 0, 1));
 
    }
 
    static long dfs(int type, int i, int j) {
        if (i == N - 1 && j == N - 1) {
            return 1;
        }
 
        if (dp[type][i][j] != -1) {
            return dp[type][i][j];
        }
 
        dp[type][i][j] = 0;
 
        if (type == 0) {        //가로인경우
            checkBlockRow(type, i, j);
            checkBlockCross(type, i, j);
        } else if (type == 1) {    //세로인경우
            checkBlockCol(type, i, j);
            checkBlockCross(type, i, j);
        } else if (type == 2) {    //대각인경우
            checkBlockRow(type, i, j);
            checkBlockCol(type, i, j);
            checkBlockCross(type, i, j);
        }
 
        return dp[type][i][j];
    }
 
    static void checkBlockRow(int type, int i, int j) {
        if (j + 1 < N && map[i][j + 1] == 0) {
            dp[type][i][j] += dfs(0, i, j + 1);
        }
    }
 
    static void checkBlockCol(int type, int i, int j) {
        if (i + 1 < N && map[i + 1][j] == 0) {
            dp[type][i][j] += dfs(1, i + 1, j);
        }
    }
 
    static void checkBlockCross(int type, int i, int j) {
        if (i + 1 < N && j + 1 < N &&
            map[i + 1][j] == 0 && map[i][j + 1] == 0 && map[i + 1][j + 1] == 0) {
            dp[type][i][j] += dfs(2, i + 1, j + 1);
        }
    }
}