[종만북] JUMPGAME 외발뛰기

문제보기

동적계획법 말고도 다른 풀이가 있을 수 있음!

아래 코드는 8장 공부하면서 따라 친 것이므로 동적계획법 중 Top Down 방식에 해당함

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

public class Main{
  static int n;
  static int[][] d; // 끝지점까지 갈 수 있는지 여부를 저장할 변수
  static int[][] map; // 주어진 지도를 저장

  // DP - Top Down
  static int jump(int i, int j){
    // 지도를 벗어난 경우 -> 0 반환하며 종료
    if( i >= n || j >= n ){ 
      return 0;
    }
    // 끝 지점에 도달한 경우 -> 1 반환하며 종료
    if( i == n-1 && j == n-1 ){
      return 1;
    }
    // 메모이제이션 된 값이 있는지 체크 - 있다면 해당 값 반환
    if(d[i][j] != -1 ){
      return d[i][j];
    }
    // 메모이제이션 된 값이 없으므로 새로 구해준다. 
    // 오른쪽으로 진행한 경우 & 왼쪽으로 진행한 경우 둘 중 하나라도 1이면 가능하다
    return d[i][j] = Math.max(jump(map[i][j]+i, j), jump(i, map[i][j]+j));
  }

  public static void main(String []args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());
    StringBuilder sb = new StringBuilder();

    while(t-->0){
      n = Integer.parseInt(br.readLine());
      map = new int [n][n];
      d = new int[n][n];
			
      // 주어진 맵을 저장함과 동시에 d 에 초기값 -1로 설정
      for(int i = 0 ; i < n ; i++ ){
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int j = 0 ; j < n ; j++){
          map[i][j] = Integer.parseInt(st.nextToken());
          d[i][j] = -1;
        }
      }
			
      sb.append(jump(0, 0) == 1 ? "YES\n" : "NO\n");

    }
    System.out.println(sb);
  }
}