백준 - 17070번 파이프 옮기기 1

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

이전 파이프의 상태에 따라서 다음 파이프가 3가지 타입으로 선택이 가능함

접근법

경우의 수를 따지는 BFS로 접근하였는데, 대부분 DP로 푼것 같다,,
TODO DP로 푸는법도 해봐야할듯

1. 끝좌표를 기준으로 BFS 탐색을 하는데, Pipe클래스를 만들어서 이전 파이프 타입을 챙김
2. curType의 값에 따라 3가지로 분기해서 경우를 따져보고, 해당되면 queue에 넣어줌
3. 현재 좌표가 끝지점이면 answer값 올려주고, 다음 경우 탐색
4. 애초에 끝지점이 1이면, 무조건 불가하니 0 출력하고 리턴

소스

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;
	}
}