[Baekjoon] 백준 17070 파이프 옮기기 1

www.acmicpc.net/problem/17070

17070번: 파이프 옮기기 1

dfs, dp로 모두 풀 수 있는 문제고 나는 dp로 풀었다.

 

파이프가 걸친 모든 영역을 신경 쓸 필요는 없고 파이프의 끝이 어디 지점에 있는지만 생각해주면 된다.

파이프의 방향에 따라 움직일 수 있는 방향이 정해져 있고

 

i, j좌표에 가로로 올 수 있는 경우, 세로로 올 수 있는경우, 대각선으로 올 수 있는 경우의 수를 더하면서 접근하면 된다.

 

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		/*
		 * Input
		 */
		int N = Integer.parseInt(scan.nextLine());
		int[][] home = new int[N+1][N+1];
		
		for(int i = 1; i<=N; i++) {
			String str = scan.nextLine();
			String[] tmp = str.split(" ");
			for(int j = 1; j<=N; j++) {
				home[i][j] = Integer.parseInt(tmp[j-1]);
			}
		}
		
		int[][][] d = new int[3][N+1][N+1];
		d[0][1][2] = 1;
		for(int i = 2; i<=N; i++) {
			if(home[1][i] == 1)
				break;
			d[0][1][i] = 1;
		}
		
		for(int i = 2; i<=N; i++) {
			for(int j = 2; j<=N; j++) {
				if(home[i][j] != 1) {
					d[0][i][j] = d[0][i][j-1]+d[2][i][j-1];
					d[1][i][j] = d[1][i-1][j] + d[2][i-1][j];
					
					if(home[i-1][j] != 1 && home[i][j-1] != 1) {
						d[2][i][j] = d[0][i-1][j-1] + d[1][i-1][j-1] + d[2][i-1][j-1];
					}
				}				
			}
		}
		
		int answer = d[0][N][N] + d[1][N][N] + d[2][N][N];
		
		System.out.println(answer);
	}
}