[BOJ] 17070 파이프 옮기기 1 (JAVA)

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

17070번: 파이프 옮기기 1

 

DP로 푸는 게 가장 빠른 것 같지만 DFS가 먼저 떠올라 DFS로 해결했습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int N, result;
	static int[][] arr;
	
	public static void main(String[] args) throws IOException {
		
		N = Integer.parseInt(br.readLine());
		arr = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		} /* 입력 끝 */
		
		link(0, 1, 0);
		System.out.println(result);
		
	}
	
	/* state : 0 가로, 1 대각, 2 세로 */
	static void link(int row, int col, int state) {

		if(row == N - 1 && col == N - 1) {
			
			result++;
			return;
			
		}
		
		int nextR = row + 1;
		int nextC = col + 1;

		// 가능하면 가로로 뻗음
		if(nextC < N && arr[row][nextC] == 0 && (state == 0 || state == 1)) {
			
			link(row, nextC, 0);
			
		}
		
		// 가능하면 대각으로 뻗음
		if(nextR < N && nextC < N && arr[row][nextC] == 0 && arr[nextR][col] == 0 && arr[nextR][nextC] == 0) {
			
			link(nextR, nextC, 1);
			
		}
		
		// 가능하면 세로로 뻗음
		if(nextR < N && arr[nextR][col] == 0 && (state == 1 || state == 2)) {
			
			link(nextR, col, 2);
			
		}
		
	}
	
}