[종만북][알고스팟] 외발 뛰기 (JUMPGAME) - 동적계획법(Dynamic Programming) JAVA

https://www.algospot.com/judge/problem/read/JUMPGAME

algospot.com :: JUMPGAME

코드설명

동적계획법을 활용합니다.

 

 

첫째, 시간초과나는 일반재귀함수를 활용하는 경우입니다.

이 경우에, 모든 경우를 가는경우 최악의 경우 2^(N*N)의 시간복잡도가 발생합니다.

즉, O(2^(N*N))입니다. 두가지 선택을 N*N번 할 수 있기 떄문입니다.

 

둘째, 중복연산을 메모이제이션(Memoization)을 활용하여 제거합니다.

이떄 흥미로운점은, cache[][]를 -1로 선언하여 합니다. 일반적으로 visited 배열을 생각하여 boolean 타입으로 방문처리를 할 것을 생각하는데, cache[][]로 -1 (아직 방문한적 자체가 없음) 0 : (방문해도 도착불가) 1 : (도착가능), 이렇게 3가지 타입으로 나누어서 생각합니다.

 

또 Bitwise OR를 활용합니다.

return cache[r][c] = (jump(r + map[r][c], c) | jump(r, c + map[r][c]));

이떄, 실수하면 안되는점은 || 를 사용하지말고 |를 사용하여 비트연산합니다.

 논리연산자로써 앞의 재귀가 만약 true(1)이라면 뒤의 true || false로, 앞의 재귀만 실행되고 중단됩니다.

사실, 반환값이 int형이기에 애초에 위의 Logical OR은 컴파일 오류 납니다.

 

 

 

코드

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = 0;
	public static int[][] map;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		while(C-- >0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			map = new int[N][N];
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				for(int j=0;j<N;j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			System.out.println(jump(0, 0) == true ? "YES" : "NO");
		}
		
	}
	
	public static boolean jump(int r, int c) {
		//기저사례 0:범위를 벗어나는경우 중단 
		if(r >= N || c >= N) return false;
		//기저사례 1: 만약 끝점에 도착한다면, true를 반환합니다.
		if(r == N-1 && c == N-1) return true;
		return ( jump(r + map[r][c], c) || jump(r, c + map[r][c])); 
	}
 
}

 

메모이제이션 활용한 코드입니다.

package Main;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, M;
	public static int answer = 0;
	public static int[][] map;
	public static int[][] cache;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		while(C-- >0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			map = new int[N][N];
			cache = new int[N][N];
			for(int i=0;i<N;i++) {
				st = new StringTokenizer(br.readLine());
				Arrays.fill(cache[i], -1);
				for(int j=0;j<N;j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			System.out.println(jump(0, 0) == 1 ? "YES" : "NO");
		}
		
	}
	
	public static int jump(int r, int c) {
		//기저사례 1 : 범위를 벗어나는경우
		if(r >= N || c >= N) return 0;
		//기저사례 2 : 끝점에 성공하는 경우
		if(r == N-1 && c == N -1) return 1;
		
		//메모이제이션 : 이미 계산한 결과라면, 
		if(cache[r][c] != -1) return cache[r][c];
		return cache[r][c] = (jump(r + map[r][c], c) | jump(r, c + map[r][c]));   
	}
 
}

 

코드 3 (반환값이 살짝 다르다. 만약, 모든 경로가 실패한경우라면 무한대를 반환한다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
	public static int C, N, K; 
	public static int answer = 0;
	public static int[][] map, cache;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		C = Integer.parseInt(st.nextToken());
		while(C-- > 0) {
			st = new StringTokenizer(br.readLine());
			N = Integer.parseInt(st.nextToken());
			map = new int[N][N];
			cache = new int[N][N];
			for(int i=0;i<N;i++) {
				Arrays.fill(cache[i], -1);
				st = new StringTokenizer(br.readLine());
				for(int j=0;j<N;j++) {
					map[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			
			answer = solve(0, 0);
			if(answer == 1) System.out.println("YES");
			else System.out.println("NO");
		}
		
		
	}
	
	public static int solve(int r, int c) {
		//기저사례 : 만약 범위를 벗어날경우
		if(r >= N || r < 0 || c < 0 || c >= N) return Integer.MAX_VALUE;
		
		if(cache[r][c] != -1) return cache[r][c];
		
		//기저사례 : 맨 끝점에 도착할경우 성공.
		if(r == N-1 && c == N - 1) return 1;
		
		int move = map[r][c];
		int ret = Math.min(solve(r + move, c), solve(r , c + move));
		return cache[r][c] = ret;
	}
	
}