[JAVA] 알고스팟 외발뛰기 - JUMPGAME 문제 해설.

프로그래밍 대회에서 배우는 알고리즘 문제해결전략 (속칭 종만북) 8단원의 동적 계획법(Dynamic Programming) 첫문제

알고스팟에서는 ID: JumpGame으로 찾으면 나오는 문제이다. 

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

문제

땅따먹기를 하다 질린 재하와 영훈이는 땅따먹기의 변종인 새로운 게임을 하기로 했습니다. 이 게임은 그림과 같이 n*n 크기의 격자에 각 1부터 9 사이의 정수를 쓴 상태로 시작합니다. 각 차례인 사람은 맨 왼쪽 윗 칸에서 시작해 외발로 뛰어서 오른쪽 아래 칸으로 내려가야 합니다. 이 때 각 칸에 적혀 있는 숫자만큼 오른쪽이나 아래 칸으로 움직일 수 있으며, 중간에 게임판 밖으로 벗어나면 안 됩니다.

균형을 잃어서 다른 발로 서거나 넘어져도 게임에서 집니다만, 재하와 영훈이는 젊고 활기차기 때문에 외발로 뛰어다니는 것은 아무것도 아닙니다. 다만 걱정되는 것은 주어진 게임판에 시작점에서 끝점으로 가는 방법이 존재하지 않을 수도 있다는 것입니다. 예를 들어 그림 (a)의 게임판에서는 사각형으로 표시된 칸들을 통해 끝에 도달할 수 있지만, 숫자가 하나 바뀐 그림 (b)에서는 그럴 수가 없습니다.

게임판이 주어질 때 왼쪽 위의 시작점에서 오른쪽 아래의 시작점에 도달할 수 있는 방법이 있는지 확인하는 프로그램을 작성하세요.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(C <= 50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 격자의 크기 n(2 <= n <= 100)이 주어지고, 그 후 n줄에 각 n개의 숫자로 왼쪽 위부터 각 칸에 쓰인 숫자들이 주어집니다. 오른쪽 아래 있는 끝 점 위치에는 0이 주어집니다.

출력

각 테스트 케이스마다 한 줄로, 시작점에서 끝 점으로 도달할 수 있을 경우 "YES"를, 아닐 경우 "NO"를 출력합니다. (따옴표 제외)

예제 입력

2
7
2 5 1 6 1 4 1
6 1 1 2 2 9 3
7 2 3 2 1 3 1
1 1 3 1 7 1 2
4 1 2 3 4 1 2
3 3 1 2 3 4 1
1 5 2 9 4 7 0
7
2 5 1 6 1 4 1
6 1 1 2 2 9 3
7 2 3 2 1 3 1
1 1 3 1 7 1 2
4 1 2 3 4 1 3
3 3 1 2 3 4 1
1 5 2 9 4 7 0 

예제 출력

YES
NO

<해결방법 및 해설> 

해설이라고 적어놓긴 했지만, 완벽히 주관적인 입장에서 적었으니 맹신하지는 않았으면 좋겠다. 틀린부분도 엄청많을 수도 있고.

사실 나는 지금 배우는 입장이고, 동적계획법을 완벽하게 짜기는 어려워서 사실상 책에서 나온대로 친것뿐이다. 

대신 조금 더 내가 이해하기 쉬운? 그리고 남이 보기에 조금 더 쉽게 풀어서 써보겠다. 

일단, 이문제는 완전탐색으로 하면 틀리는 문제다. 3000ms이기때문에, 시간이 부족해서 중복되는 결과를 바로바로 처낼수 있어야한다.

그것이 완전탐색과 이 동적계획법이 가지는 큰 차이점이겠다. 그럼 그걸 어떻게 할거냐?

중복값이 나오면 무조건 그값을 리턴하고 그 후 무시하고 진행하는 것으로 실행시키면된다.

처음에 나는 이 함수폼이 int값을 return하는 것이 이해가 잘 안갔는데, 이 중복값을 return시키기 위해서 꼭 int 값을 해야한다.  

boolean으로 하면 완전탐색꼴이되서 시간초과가 날것임.

그리고 답을 출력할때

 0을 리턴하는 경우 1을 리턴하는 경우를 명확하게 판단해서 조건문 쓸때 잘써야됨. ㅋㅋ 괜히 값이 역으로 나올 수도 있고, 다 맞춰놓고 답이 틀리는 경우가 있다. 

7
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 2
1 1 1 1 1 2 0 

테스트 케이스중에서 자신의 코드가 잘 돌아가는지 확인해보기 쉬운 꼴중 하나이다. 

무조건 NO가 나와야되고, 저기서 2부분을 1로 바꾸면 무조건 YES가 나와야한다.

import java.util.*;


public class JumpGame {
	static int n;
	static int board [][] = new int[100][100];
	static int cache[][] = new int[100][100];
	static int ret = 0;
	static int jump(int y, int x){
		if(y>=n || x>= n){
			return 0; //이건 x나 y가 보 범위 벗어나면 0을 출력~ 
		}
		if(y ==n-1 && x==n-1){
			return 1;// 끝지점에 도착하는게 이거임. 1
		}
		
		if(cache[y][x] != -1){
			return cache[y][x];
		}
		int jumpSize = board[y][x];
		return cache[y][x] = jump(y+jumpSize, x) | jump(y, x+jumpSize);
	}
	
	public static void main(String[] args) {
		Scanner input = new Scanner (System.in);
		int tc = input.nextInt();
		while(tc>0){
			 n = input.nextInt(); 
			//해맨부분 -> 전역변수를 활용하지 못했다. int N이라고 써놓고 삽질함. 즉, 이소리는 jump함수안에는 n크기를 판단해서 돌아가는데, 이건 모른다는것.
			for(int i=0; i<n; i++){
				for(int j=0; j<n; j++){
						board[i][j] =input.nextInt();
						cache[i][j] = -1; 
						//해맨 부분은 cache 초기화 안해줘서 000으로 초기화 되있어서 0나올리는 없겠지만,만약나왔다면 오류나서 문제 아마틀렸을거임.
				}
			}
			if(jump(0,0)==1){ // 함수작동시키는 법은 대충 이럼 (0,0)처럼 시작지점에 스타트만 시켜주면 자기가 알아서 굴러가는 거지 
				System.out.println("YES");
			}
			if(jump(0,0)!=1){
				System.out.println("NO");
			}
			// 이거말고도 4줄을 단 한줄에 적어버리는 방법이 있더라~)
//			//System.out.println (jump(0,0) !=0 ? "YES" : "NO");
//			
//			tc--;
		}
	}


}




?????

<사견 & 후기>

근데 그 책을 보면서 해도 조금의 문제점이 있기 마련이다.

책의 주력언어는 C++로 알고 있는데, 나는 Java로 하기 때문에 그 차이가 명확하게 튀어나온다. 

예를들면,  int& ret =cache[][]; 이런 구문이 있는데 처음에는 나는 이게 뭔지 몰랐다.  (뭐라는 거야 쉬밤... 이러고 있었음)

근데 앞뒤 설명을 대략적으로 유추를 해서  그리고 책에서도 말하는 참조형이라는 데 유의하세요! 

int& ret은 전역변수를 말하는 것이라는 걸 알아감,

즉, 자바에서는 static int ret으로 써야지 굴러가는 구문인것.

전역변수를 설정하는 다른 방법이 있겠으나, 아직 내 지식으로는 전역변수를 설정하는게 static int 가 가장 안전하다고 판단했다.

주석에 내가 해맨 부분들이 있다. 아마 그런 부분에서 실수하기 쉬운 문제 인것 같다. 

그리고 논리적으로는 어떤식으로 굴러가는지 알기 쉬운 데 반면 코드를 실행시키고 내가 원한 값이 안나오는 대표적인 재귀함수꼴문제라서 디버깅하기도 쉽지 않더라..

아직 코드 뉴비라서 재귀함수 문제는 디버깅을 어떤식으로 해야지 잘 모르겠다.

참조: 도움을 많이 받은 사이트들 같이 보면 좋다!..

http://redscreen.tistory.com/169

https://github.com/congr/world/blob/master/algospot/JumpGame.java

http://gwpark.tistory.com/1812