알고스팟 JUMPGAME(외발뛰기) Java로 구현하기

안녕하세요. Message입니다.

오늘은 알고스팟의 JUMPGAME(외발뛰기) 문제를 Java로 풀이하는 포스팅입니다.

문제링크 : https://algospot.com/judge/problem/read/JUMPGAME

 

 

1. 재귀를 이용한 완전탐색 + 동적 계획법 

이 문제를 푸는 포인트는 재귀를 이용한 완전탐색을 구현한 뒤에

이미 탐색한 결과를 재활용하는 메모이제이션(Memoization)을 이용하여 탐색 횟수를 줄여야합니다.

만약 동적 계획법을 적용하지 않았을 경우에는 아래처럼 엄청난 차이가 발생하게 됩니다.

당연히 제한 시간인 2초를 넘겨버리기 때문에 '시간초과' 문구가 뜨게됩니다.

  

 

2. Java로 구현 

언제나 말로 풀어쓴 문제를 코드화 하는건 익숙해지기 전까지 참 어려운 일인듯 합니다.

어느정도 머리로 이해가 됐어도 막상 구현하려고 하면 손이 얼음이 되니까요.

아래 2가지를 먼저 구상하고 코드를 구현하면 어느정도 길이 잡힐 듯 싶네요.

1. 지속적으로 호출되는 다음 재귀 함수에 어떤 값을 넣어줄 것인가? -> 게임판 x, y 좌표값

2. 재귀함수를 탈출하는 조건은 무엇인가?

   - 목표가 달성되었을 경우 --> 함수의 인자로 받은 좌표값이 게임판의 끝인 경우

   - 예외가 발생한 경우 --> 함수의 인자로 받은 좌표값이 게임판을 벗어난 경우

3. 무엇을 리턴할 것인가? --> 목표에 도달했으면 True, 예외가 발생한 경우 False

 

이를 바탕으로 구현한 코드는 아래와 같습니다.

package Algospot;
import java.util.Arrays;
import java.util.Scanner;
 
 
public class Main {
    int[][] matrix;
    int[][] cache;
    int n;
    
    Main(int[][] matrix){
        n = matrix.length;
        this.matrix = matrix;
        this.cache = new int[n][n];
        for(int[] arr : this.cache)
            Arrays.fill(arr, -1);
    }
    
    public boolean solve(int x, int y){
        
        // 게임판의 범위를 벗어남
        if(x >= n || y >= n) return false;
        
        // 목표지점에 도달
        if(x==n-1 && y==n-1) return true;
        
        // 메모이제이션
        if(cache[x][y] == 1) return false;
        else cache[x][y] = 1;
        
        int jump = matrix[x][y];
        return solve(x+jump, y) || solve(x, y+jump);
    }
    
    
    public static void main(String[] args) {
        
        int[][] matrix;
        int n;
        
        Scanner sc = new Scanner(System.in);
        int numTestCase = sc.nextInt();
        
        for(int i = 0; i<numTestCase; i++){
            n = sc.nextInt();
            matrix = new int[n][n];
            for(int x=0; x<n; x++){
                for(int y=0; y<n; y++){
                    matrix[x][y] = sc.nextInt();
                }
            }
            
            Main main = new Main(matrix);
            boolean res = main.solve(0,0);
            System.out.println(res? "YES":"NO");
        }
    }
}
 

 

개인적으로 구현한 코드와 알고리즘 문제해결 전략 책에 나온 답안이 얼추 비슷하긴 했지만

책에 소개된 리턴 방식이 좀더 간결해 보여서 적용했습니다.

==> return solve(x+jump, y) || solve(x, y+jump);

함수 리턴값이 Boolean 형이라면 이런 패턴을 기억하고 있다가 써먹으면 좋을 듯 싶네요.

아래 구문은 구글링을 하다보니 알게된 문법입니다. 알아두면 간결한 코드를 짜는게 도움이 될 것 같습니다.

System.out.println(res? "YES":"NO");

 

언제나 결과만 보면 뭐 이런걸로 고민을 했나 싶을 정도로 간단해보이네요..ㅜ

이만 포스팅을 마칩니다.

 

 

posted By Message

Commit your way to the LORD, trust in him and he will do this. [PSALms 37:5]

redScreen.tistory.com Blog :(