코테_백준_17070_파이프 옮기기 1

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

17070번: 파이프 옮기기 1

 

접근 방법

해당 문제는 DP로 접근하고 풀었다.

파이프의 종류는 가로, 세로, 대각선으로 3가지 종류가 있고, 가로에서 세로로 또는 세로에서 가로로 바로 변경할 수 없는게 해당 문제의 특징이다. 이에 DP는 3가지 종류의 Map(가로, 세로, 대각선)으로 나눠 접근한다.

현재 파이프 종류에 따라 다음 파이프의 종류가 나뉘는 것은 다음과 같다.

• 가로 파이프 : 가로, 대각선 파이프
• 세로 파이프 : 세로 , 대각선 파이프
• 대각선 파이프 : 가로, 세로, 대각선 파이프

반대로 말하면 현재 파이프의 종류를 통해 전 파이프가 어떤 종류였는지 경우의 수를 예측할 수 있다. 해당 경우를 따져서 현재 칸에 나올 수 있는 경우의 수를 더해주면 된다.

 

코드

class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        //실제 Map
        int[][] table = new int[N + 1][N + 1];
        //차원(가로, 세로, 대각선), 행, 열
        int[][][] dp = new int[3][N + 1][N + 1];

        for (int row = 1; row <= N; row++) {
            st = new StringTokenizer(br.readLine());
            for (int col = 1; col <= N; col++)
                table[row][col] = Integer.parseInt(st.nextToken());
        }
        dp[0][1][2] = 1;

        for (int row = 1; row <= N; row++) {
            for (int col = 1; col <= N; col++) {
            	//현재 칸이 벽이라면 경우의 수는 0이다.
                if (table[row][col] == 1)
                    continue;
				
                //현재 파이프가 가로라면 이전 파이프는 가로 또는 대각선 파이프이다. 가로와 대각선 파이프의 경우의 수를 더한다.
                dp[0][row][col] += dp[0][row][col - 1] + dp[2][row][col - 1];
                
                //현재 파이프가 세로라면 이전 파이프는 세로 또는 대각선 파이프이다. 세로와 대각선 파이프의 경우의 수를 더한다.
                dp[1][row][col] += dp[1][row - 1][col] + dp[2][row - 1][col];
				
                //현재 파이프가 대각선인 경우라는 것은 이전 칸에 벽이 존재하지 않아야 한다.
                if (table[row - 1][col] == 0 && table[row][col - 1] == 0)
                	//현재 파이프가 대각선이라면 이전 파이프는 가로, 세로, 대각선 파이프이다.
                    dp[2][row][col] += dp[0][row - 1][col - 1] + dp[1][row - 1][col - 1] + dp[2][row - 1][col - 1];
            }
        }
        System.out.println(dp[0][N][N] + dp[1][N][N] + dp[2][N][N]);
    }
}