문제 접근

기본적으로 N이 16이하이기 때문에 굳이 dp를 적용하지 않고 브루트포스로 풀어도 된다.
하지만, 어차피 연습하는 것이고 공부하는 것이니 더 좋은 방법인 dp로 풀어보려고 했다.
실제로 시간 차이가 거의 2.5배 정도 났다.

우선, dp로 풀고 싶다면 파이프의 끝이 위치한 곳을 기준으로 특정 방향에 놓여있을때, 그 곳부터 시작해서 끝까지 모든 케이스를 둘러본 경우 중 N-1, N-1에 도달할 수 있는 모든 케이스를 dp테이블에 저장하면 된다. 때문에 dp테이블은 3차원 테이블이여야 한다.
[x축][y축][방향 = 0,1,2]
나는 가로 방향은 0, 세로방향은 1, 대각방향은 2로 했다.

문제 풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int N;
    static int[][] map;

    static int[][][] dp;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        map = new int[N][N];

        dp = new int[N][N][3];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                for (int k = 0; k < 3; k++) {
                    dp[i][j][k] = -1;
                }
            }
        }

        StringTokenizer st;
        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());
            }
        }

        System.out.println(move(0, 0, 0, 1));
    }

    private static int move(int x1, int y1, int x2, int y2) {
        if (x2 == N - 1 && y2 == N - 1) {
            return 1;
        }

        int count = 0;
        if (x2 - x1 == 0 && y2 - y1 == 1) { // 가로이면
            if (dp[x2][y2][0] == -1) {
                count += moveIfPossibleToHorizontal(x2, y2, x2, y2 + 1);
                count += moveIfPossibleToDiagonal(x2, y2, x2 + 1, y2 + 1);
                dp[x2][y2][0] = count;
            } else {
                count += dp[x2][y2][0];
            }
        } else if (x2 - x1 == 1 && y2 - y1 == 0) { // 세로이면
            if (dp[x2][y2][1] == -1) {
                count += moveIfPossibleToVertical(x2, y2, x2 + 1, y2);
                count += moveIfPossibleToDiagonal(x2, y2, x2 + 1, y2 + 1);
                dp[x2][y2][1] = count;
            } else {
                count += dp[x2][y2][1];
            }
        } else { // 대각 상태인 경우
            if (dp[x2][y2][2] == -1) {
                count += moveIfPossibleToHorizontal(x2, y2, x2, y2 + 1);
                count += moveIfPossibleToVertical(x2, y2, x2 + 1, y2);
                count += moveIfPossibleToDiagonal(x2, y2, x2 + 1, y2 + 1);
                dp[x2][y2][2] = count;
            } else {
                count += dp[x2][y2][2];
            }
        }
        return count;
    }

    private static int moveIfPossibleToHorizontal(int x1, int y1, int x2, int y2) {
        if (isIn(x2, y2) && map[x2][y2] == 0) {
            return move(x1, y1, x2, y2);
        }
        return 0;
    }

    private static int moveIfPossibleToVertical(int x1, int y1, int x2, int y2) {
        if (isIn(x2, y2) && map[x2][y2] == 0) {
            return move(x1, y1, x2, y2);
        }
        return 0;
    }

    private static int moveIfPossibleToDiagonal(int x1, int y1, int x2, int y2) {
        if (isIn(x2, y2) && map[x2][y2] == 0 && map[x2 - 1][y2] == 0 && map[x2][y2 - 1] == 0) {
            return move(x1, y1, x2, y2);
        }
        return 0;
    }

    private static boolean isIn(int x, int y) {
        return x >= 0 && x < N && y >= 0 && y < N;
    }
}

처음은 dfs 기반의 브루트 포스로 풀었고, 다음은 dp를 적용한 위 풀이 결과이다. 거의 2.5배 시간 차이가 난다.