[백준 17070] 파이프 옮기기1 / 자바 / dp

#문제         

레벨: G5
알고리즘: dp 
풀이시간: 1시간
힌트 참조 유무: 유

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

---

#문제 설명    

문제에서 놓칠 수도 있는 부분 몇 가지만 짚고 넘어가겠습니다.

1. 파이프는 90~180도까지 +45도 or -45만 움직일 수 있다.

2. 대각선 파이프는 4칸을 차지한다. 그 4칸 중 벽(1)이 있으면 안 된다.

 

이 문제는 dfs 또는 dp로 풀 수 있습니다. dfs로 풀 수 있는 이유는 입력최대값이 작아서 그렇습니다. 저는 dp를 공부중이기 때문에 dp를 사용해서 풀겠습니다. 

---

#알고리즘 설명   

dp를 알려면 이 유형은 꼭 알아두었으면 좋겠습니다. 이 문제에서 어떻게 dp를 이용하냐면, 각 위치에 도착할 수 있는 경우의 수를 담는 것입니다.

이 문제에서만 특별한 점은 45도 씩만 움직여야 하기 때문에 가로가 세로가 될 수 없고 세로가 가로로 될 수 없습니다. 그래서 가로,대각선, 세로로 나누어 도착할 수 있는 경우의 수를 저장하는 것입니다.

dp[i][j][0]  i,j에 가로파이프로 도착한 경우의 수

dp[i][j][1]  대각선

dp[i][j][2]  세로

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[][] house = new int[N][N];

        // 집의 상태 입력 받기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                house[i][j] = scanner.nextInt();
            }
        }

        System.out.println(countPipeMovements(N, house));
        scanner.close();
    }

    public static int countPipeMovements(int N, int[][] house) {
        // dp[r][c][d]: (r,c)에 파이프의 끝이 있고, 방향이 d일 때 가능한 경우의 수
        // d: 0=가로, 1=세로, 2=대각선
        int[][][] dp = new int[N][N][3];

        // 초기 상태: (0,1)에 가로로 놓인 파이프
        dp[0][1][0] = 1;

        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (house[r][c] == 1) continue;

                // 가로 방향으로 이동
                if (c > 0 && house[r][c-1] == 0) {
                    dp[r][c][0] += dp[r][c-1][0] + dp[r][c-1][2];
                }

                // 세로 방향으로 이동
                if (r > 0 && house[r-1][c] == 0) {
                    dp[r][c][1] += dp[r-1][c][1] + dp[r-1][c][2];
                }

                // 대각선 방향으로 이동
                if (r > 0 && c > 0 && house[r-1][c] == 0 && house[r][c-1] == 0 && house[r-1][c-1] == 0) {
                    dp[r][c][2] += dp[r-1][c-1][0] + dp[r-1][c-1][1] + dp[r-1][c-1][2];
                }
            }
        }

        // (N-1, N-1)에 도달하는 모든 경우의 합
        return dp[N-1][N-1][0] + dp[N-1][N-1][1] + dp[N-1][N-1][2];
    }
}