[백준] 17070번 파이프 옮기기 1 (gold 5

import java.io.*;
import java.util.*;

class Point{
    int x;
    int y;
    int v;
    public Point(int x, int y, int v){
        this.x=x;
        this.y=y;
        this.v=v;
    }
}
public class Main{
    static int n;
    static  int[][] map;
    public static void main(String[] args )throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        n=Integer.valueOf(br.readLine());
        map=new int[n+1][n+1];

        for(int i=1; i<=n; i++){
            st=new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++){
                map[i][j]=Integer.valueOf(st.nextToken());
            }
        }
        //가로 0 //세로 1 //대각선 2
        Queue<Point> que=new LinkedList<>();
        que.offer(new Point(2,1,0));

        int answer=0;
        if(map[n][n]!=1) {
            while (!que.isEmpty()) {
                Point temp = que.poll();
                if (temp.x == n && temp.y == n) {
                    answer++;
                } else if (temp.v == 0) {
                    if (cross(temp.x, temp.y)) {
                        que.offer(new Point(temp.x + 1, temp.y, 0));
                    }
                    if (dakak(temp.x, temp.y)) {
                        que.offer(new Point(temp.x + 1, temp.y + 1, 2));
                    }

                } else if (temp.v == 1) {
                    if (dakak(temp.x, temp.y)) {
                        que.offer(new Point(temp.x + 1, temp.y + 1, 2));
                    }
                    if (height(temp.x, temp.y)) {
                        que.offer(new Point(temp.x, temp.y + 1, 1));
                    }
                } else {
                    if (cross(temp.x, temp.y)) {
                        que.offer(new Point(temp.x + 1, temp.y, 0));
                    }
                    if (dakak(temp.x, temp.y)) {
                        que.offer(new Point(temp.x + 1, temp.y + 1, 2));
                    }
                    if (height(temp.x, temp.y)) {
                        que.offer(new Point(temp.x, temp.y + 1, 1));
                    }
                }

            }
        }
        bw.write(answer+"");
        bw.flush();
    }

    public static boolean cross(int x, int y){
        if(x+1>n || map[y][x+1]==1){
            return false;
        }
        else {
            return true;
        }
    }
    public static boolean height(int x, int y){
        if(y+1>n || map[y+1][x]==1){
            return false;
        }
        else {
            return true;
        }
    }
    public static boolean dakak(int x, int y){
        if(x+1>n || y+1>n || map[y][x+1]==1 || map[y+1][x]==1 || map[y+1][x+1]==1){
            return false;
        }
        else {
            return true;
        }
    }
}

// bfs를 이용한 풀이 하지만, 80%부근의 테스트케이스가 n이 16인 케이스. 이때 que에 들어가는 
// 노드의 수가 계속해서 3혹은 2의 지수로 증가하기 때문에 엄청난 갯수가 들어가서 시간초과를 발생한다.
// 따라서 bfs로는 16인 경우, 마지막이 벽이라 그 예외만 처리하면 정답으로 통과가 되지만 사실상 완전한
// 풀이는 아니다. dfs로 길을 하나하나 찾아가야 노드에 많은 수가 몰리는걸 막을 수 있기 때문이다.
// (visit으로 방문처리도 안되고 갔던 지점을 다른 곳에서 다시 도달하는 경우들도 많ㅇ므.
// 따라서 dp를 이용한 풀이를 해야 적절하다.

// cpp에서는 dfs도 통과. 하지만 추가시간이 없어서 java나 python을 이용해서는 통과가 안됨.

import java.io.*;
import java.util.*;

public class Main{
    static int n;
    static  int[][] map;
    static  int[][][] dp;
    public static void main(String[] args )throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        n=Integer.valueOf(br.readLine());
        map=new int[n+1][n+1];

        for(int i=1; i<=n; i++){
            st=new StringTokenizer(br.readLine());
            for(int j=1; j<=n; j++){
                map[i][j]=Integer.valueOf(st.nextToken());
            }
        }

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


        dp[1][2][0]=1;
        //가로 0 //세로 1 //대각선 2
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                if(map[i][j]==1){
                    continue;
                }
                dp[i][j][0]+=dp[i][j-1][0];
                dp[i][j][0]+=dp[i][j-1][2];

                dp[i][j][1]+=dp[i-1][j][1];
                dp[i][j][1]+=dp[i-1][j][2];

                if(dakak(j,i)) {
                    dp[i][j][2] += dp[i - 1][j - 1][2];
                    dp[i][j][2] += dp[i - 1][j - 1][0];
                    dp[i][j][2] += dp[i - 1][j - 1][1];
                }

            }
        }


        bw.write(dp[n][n][0]+dp[n][n][1]+dp[n][n][2]+"");
        bw.flush();
    }
    
    public static boolean dakak(int x, int y){
        if(map[y][x-1]==1 || map[y-1][x]==1 || map[y][x]==1){
            return false;
        }
        else{
            return true;
        }
    }
}

// dp를 이용한 풀이
// 여기서 세가지 경우 즉 가로 , 세로, 대각선의 케이스가 있으므로 각각의 다른 배열방에 값 저장하고.
// 이를 이용해서 풀이를 해나가면된다.