BOJ 17070 java 풀이

DP 문제이고 (BFS 쓰면 시간초과남)

중요한건 결국 "해당 위치에 도달하는 방법을 구하면 된다"

예를 들어 왼쪽으로 오는 방법은 왼쪽/대각선, 세로로 오는 방법은 세로/대각선, 대각선으로 오는 방법은 왼쪽/세로/대각선

그래서 그 이전에 있던 방법들을 구하면 됨

 

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[][] map = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                map[i][j] = sc.nextInt();
            }
        }

        int[][][] dp = new int[3][n][n];

        dp[0][0][1] = 1;

        for (int i = 0; i < n; i++) {
            for (int j = 2; j < n; j++) {
                if (map[i][j] == 1) continue;

                // 왼쪽으로 오는 방법은 왼쪽/대각선에서 온거
                dp[0][i][j] = dp[0][i][j - 1] + dp[1][i][j - 1];

                // 세로로 오는건 다음줄부터 가능
                // 세로로 오는 방법은 세로/대각선에서 온거
                if (i > 0) {
                    dp[2][i][j] = dp[2][i - 1][j] + dp[1][i - 1][j];
                }
                
                // 대각선은 다음줄부터 가능 + 길막 없어야 가능
                // 대각선으로 오는 방법은 왼쪽/세로/대각선에서 온거
                if (i > 0 && map[i - 1][j] == 0 && map[i][j - 1] == 0) {
                    dp[1][i][j] = dp[0][i - 1][j - 1] + dp[1][i - 1][j - 1] + dp[2][i - 1][j - 1];
                }
            }
        }

        // 왼쪽/대각선/세로에서 여기 오는 방법 다 더하면 됨
        int result = dp[0][n - 1][n - 1] + dp[1][n - 1][n - 1] + dp[2][n - 1][n - 1];
        System.out.println(result);
    }
}