백준 17069 파이프옮기기2

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

17069번: 파이프 옮기기 2

 

파이프를 가로 세로 대각선으로만 이동할 수 있고, 회전할때 45도로만 회전할수 있다.

 

그러므로 가로로 갈수 있는 방법은 가로 => 가로 대각선 =>가로이고,

세로로 갈수 있는 방법은 세로 =. 세로, 대각선 => 세로이며,

대각선으로 갈수 잇는 방법은 가로 => 대각선, 세로 => 대각선, 대각선 => 대각선이다.

(물론 중간에 장애물이 있으면 안된다.)

dp[dir][i][j] 가 i,j 에서 dir 방향으로 갈수 있는 경우수라고 하면(dir : 0 가로 dir : 1대각선 dir : 2 세로 라고 하먄)

다음과 같은 점화식이 만들어진다.

이 dp 점화식을 i= 0 ~N j = 0~ N 까지 모두 돌려준뒤

마지막 점인 N-1, N-1에서 dp배열의 총 합만 구해주면된다.

이 알고리즘의 시간 복잡도는 O(N^2), 공간 복잡도는 O(N^2)이다.

if(j+1< N && map[i][j+1] == 0 ) {//장애물 체크
					dp[0][i][j+1] += dp[0][i][j]; //가로 => 가로
					dp[0][i][j+1] += dp[1][i][j]; //대각선 => 가로
				}
				if(j+1<N && i+1 <N && map[i+1][j]==0 && map[i+1][j+1]==0 && map[i][j+1] ==0) {
					dp[1][i+1][j+1] += dp[0][i][j]; //가로 => 대각선
					dp[1][i+1][j+1] += dp[2][i][j]; //세로 => 대각선
					dp[1][i+1][j+1] += dp[1][i][j]; //대각선 => 대각선
				} //대각선 이동
				
				if(i+1<N && map[i+1][j]==0) {
					dp[2][i+1][j] += dp[2][i][j]; //세로 => 세로
					dp[2][i+1][j] += dp[1][i][j];//대각선 => 세로
					
				}//세로 이동

 

 

 

 

 

package 백준;

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

public class 파이프옮기기2 {
	static class MyScanner{
		BufferedReader bf;
		StringTokenizer st;
		MyScanner(){
			bf = new BufferedReader(new InputStreamReader(System.in));
		}
		
		String next() {
			while(st==null||!st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(bf.readLine());
				} catch (IOException e) {
					// TODO Auto-generated catch block
					e.printStackTrace();
				}
			}
			
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		
		
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		MyScanner sc = new MyScanner();
		int N = sc.nextInt();
		int map[][] = new int[N][N];
		long dp[][][] = new long[3][N][N];
		
		for(int i =0 ;i <N;i++) {
			for(int j=0 ; j <N;j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		dp[0][0][1] = 1; //0 가로 1 대각선 2 세로
		
		for(int i =0 ;i < N;i++) {
			for(int j= 0;j<N;j++) {
				
				if(j+1< N && map[i][j+1] == 0 ) {//가로로 한칸이동
					dp[0][i][j+1] += dp[0][i][j];
					dp[0][i][j+1] += dp[1][i][j];
				}
				if(j+1<N && i+1 <N && map[i+1][j]==0 && map[i+1][j+1]==0 && map[i][j+1] ==0) {
					dp[1][i+1][j+1] += dp[0][i][j];
					dp[1][i+1][j+1] += dp[2][i][j];
					dp[1][i+1][j+1] += dp[1][i][j];
				} //대각선 이동
				
				if(i+1<N && map[i+1][j]==0) {
					dp[2][i+1][j] += dp[2][i][j];
					dp[2][i+1][j] += dp[1][i][j];
					
				}//세로 이동
				
			}
		}
		
		long answer = 0;
		for(int i =0 ;i <3;i++) {
			answer+=dp[i][N-1][N-1];
		}
		System.out.println(answer);
		
		
	}

}