[JAVA] 백준 1890번 : 점프

 

1890번: 점프

 

문제

NXN 게임판에 수가 적혀져 있다.

게임의 목표 :  가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것

각 칸에 적혀 있는 수 : 현재 칸에서 갈 수 있는 거리

-> 반드시 오른쪽이나 아래로 가야함.

-> 한 번 점프를 할 때, 방향을 바꾸면 안됨.

-> 한 칸에서 오른쪽으로 점프를 하거나, 아래로 점프를 하는 두가지 경우만 존재.

 

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 개수를 구하는 프로그램

 

입력

첫째 줄 : 게임 판의 크기  N (4 ≤ N ≤ 100)

그 다음 N개 줄 : 각 칸에 적혀져 있는 수가 N개씩 주어짐. 

-> 칸에 적혀있는 수는 0보다 크고 9보다 작거나 같은 정수

-> 가장 오른쪽 아래 칸에는 항상 0

 

출력

가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 문제의 규칙에 맞게 갈 수 있는 경로의 개수를 출력.

경로의 개수는 2^63-1보다 작거나 같다.

 

풀이

게임판에 적혀있는 정수들의 배열을 list[][], 그 칸에 도착하게되는 경로의 개수를 dp[][]라고 하면

각 칸에 적혀져 있는 수만큼 오른쪽 or 아래방향으로 움직이게 되니까

list[i][j]에서의 다음 이동 칸은 list[i+list[i][j]][j] 또는 list[i][j+list[i][j]], 이 두가지 경우가 될 수 있다.

즉, 다음으로 도착하게 되는 이동칸에 이전 칸까지 오는 경로의 개수를 더해주면 된다.

dp[i+list[i][j]][j] += dp[i][j], dp[i][j+list[i][j]] += dp[i][j] 인 셈이다.

이 때, i+list[i][j] 와 j+list[i][j]는 N보다 같거나 작은 범위에서만 가능하다.

 

이런식으로 진행된다.

왼쪽이 게임판인 list, 오른쪽이 경로의 개수를 더하는 dp이다.

public class bj1890 {
	static int n;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s = new Scanner(System.in);
		
		n= s.nextInt(); // 게임판의 크기
		int list[][] = new int[n+1][n+1];
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				list[i][j] = s.nextInt();
			}
		}
		
		long dp[][] = new long[n+1][n+1]; // 경로의 개수는 2^63-1보다 작거나 같으니 long타입
		dp[1][1]=1;
		
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				int next = list[i][j];
				if(next==0) break;
				// if(i==n&&j==n) continue;// 위에랑같은문장.. 해당 반복문만 빠져나감.
				if(j+next<=n) dp[i][j+next] += dp[i][j];
				if(i+next<=n) dp[i+next][j] += dp[i][j];
			}		
			
			// dp 변화 출력확인
			//print(dp);
            //System.out.println();
		}
		System.out.println(dp[n][n]);
	}
	 public static void print(long[][] dp){
	        for(int i=1; i<=n; i++){
	            for(int j=1; j<=n; j++){
	                System.out.print(dp[i][j]+" ");
	            }
	        System.out.println();
	        }
	        
	  }
}