https://www.acmicpc.net/problem/17070
이전 파이프의 상태에 따라서 다음 파이프가 3가지 타입으로 선택이 가능함
경우의 수를 따지는 BFS로 접근하였는데, 대부분 DP로 푼것 같다,,
TODO
DP로 푸는법도 해봐야할듯
Pipe
클래스를 만들어서 이전 파이프 타입을 챙김import java.util.*;
import java.io.*;
public class Main {
static int N;
static int[][] Array;
static int Answer = 0;
static int[][] Dir = {{0,1}, {1,1},{1,0}}; //가로는 0, 1 / 대각선은 0, 1, 2 / 세로는 1, 2
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
Array = new int[N][N];
for(int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j < N; j++) {
Array[i][j] = Integer.parseInt(st.nextToken());
}
}
if(Array[N-1][N-1] == 1) {
System.out.println(0);
return;
}
Queue<Pipe> q = new LinkedList<Pipe>();
q.offer(new Pipe(0, 1, 0)); // (0, 1) 좌표에 가로로 놓임
while(!q.isEmpty()) {
Pipe curPipe = q.poll();
int curX = curPipe.x;
int curY = curPipe.y;
if(curX == N-1 && curY == N-1) {
Answer++;
continue;
}
int curType = curPipe.type;
for(int i = 0; i < Dir.length; i++) {
int nextX = curX + Dir[i][0];
int nextY = curY + Dir[i][1];
if(nextX >= N || nextY >= N || Array[nextX][nextY] == 1) continue; //범위밖은 무조건 아웃
if(curType == 0) {
if(i == 0) q.offer(new Pipe(nextX, nextY, 0));
else if(i == 1 && Array[curX][curY+1] == 0 && Array[curX+1][curY+1] == 0 && Array[curX+1][curY] == 0) {
q.offer(new Pipe(nextX, nextY, 1));
}
} else if(curType == 1) {
if(i == 0) q.offer(new Pipe(nextX, nextY, 0));
else if(i == 1 && Array[curX][curY+1] == 0 && Array[curX+1][curY+1] == 0 && Array[curX+1][curY] == 0) {
q.offer(new Pipe(nextX, nextY, 1));
} else if(i == 2) q.offer(new Pipe(nextX, nextY, 2));
} else {
if(i == 1 && Array[curX][curY+1] == 0 && Array[curX+1][curY+1] == 0 && Array[curX+1][curY] == 0) {
q.offer(new Pipe(nextX, nextY, 1));
} else if(i == 2) q.offer(new Pipe(nextX, nextY, 2));
}
}
}
System.out.println(Answer);
}
}
class Pipe{
int x;
int y;
int type; // 가로 0,대각선 1, 세로 2
Pipe(int x, int y, int type) {
this.x = x;
this.y = y;
this.type = type;
}
}