백준 1890번 : 점프

문제 링크 : https://www.acmicpc.net/problem/1890

문제를 해결하기 위해 처음에 재귀함수만을 사용하여 dfs 풀이로 풀어보았다. 하지만, 재귀를 이용한 dfs로 풀면 메모리 초과가 떠 문제를 해결할 수가 없었다. 메모리 초과가 뜬 코드는 아래와 같다.

import java.util.Scanner;

public class Main {

  public static int Move(int[] xy, int[][] Map, int ans){
    if(xy[0] >= Map[0].length || xy[1] >= Map[0].length){
      return 0;
    }
    if(Map[xy[0]][xy[1]]==0){
      ans++;
      return ans;
    }

    int[] pos1 = {xy[0]+Map[xy[0]][xy[1]], xy[1]};
    int[] pos2 = {xy[0], xy[1]+Map[xy[0]][xy[1]]};
    int a = Move(pos1, Map, ans);
    int b = Move(pos2, Map, ans);
    return a+b;
  }


  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    int N = sc.nextInt();

    int[][] map = new int[N][N];

    for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
        map[i][j]=sc.nextInt();
      }
    }
    sc.close();



    int[] pos = {0, 0};
    int answer=0;
    answer = Move(pos, map, answer);

    System.out.println(answer);


  }
}

 

그래서 이걸 어떻게 해결해야하나,, 싶었다.

먼저, 재귀를 이용한 dfs는 뭐고, dp는 뭔지 부터 찾아보았다.
결론부터 말하자면, 재귀를 이용한 dfs는 그냥 트리나 그래프 같은 곳에서 사용하면된다.

 

	장점	단점
DFS	간단하고 직관적인 구현이 가능하다. 깊이 우선 탐색으로 모든 가능한 경로를 탐색하므로 정확한 해를 구할 수 있다.	중복 계산이 발생할 수 있어 효율성이 떨어진다. 최적 부분 구조를 활용하지 못해 중복 계산이 많아질 수 있다.
DP	중복 계산을 피하고 이전에 계산한 값을 저장해 재활용할 수 있다. 최적 부분 구조를 활용하여 효율적으로 해결할 수 있다.	구현이 좀 더 복잡하고 추상적일 수 있다. 모든 상태를 저장해야 하므로 공간 복잡도가 높아질 수 있다.

 

그래서 아래 참조에 있는 블로그에서 참조하여 문제를 해결하였다. 24.1.3에 제가 해석한 바로는 dp라는 칸에다가 각 상황에 대한 정답을 한땀한땀 적어 문제를 해결한 것이다. 근데 DFS와 DP의 사용의 차이는 알겠는데 엄밀한 차이는 모르겠다. 결국 모든 경로를 탐색하는데,,
아님 아래 코드는 DP가 아닌가..? 싶네 뭐지 더 알아보겠습니다.

 

정답

import java.util.Scanner;

public class Main {
  static int N;
  public static long Jump(long[][] dp, int[][] Map){

    for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
        int moveCnt = Map[i][j];
        if(i == N-1 && j == N-1){
          return dp[N-1][N-1];
        }
        if(i+moveCnt<N){
          dp[i+moveCnt][j] += dp[i][j];
        }
        if(j+moveCnt<N){
          dp[i][j+moveCnt] += dp[i][j];
        }
      }
    }
    return -1;
  }


  public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);

    N = sc.nextInt();

    int[][] map = new int[N][N];

    for(int i=0;i<N;i++){
      for(int j=0;j<N;j++){
        map[i][j]=sc.nextInt();
      }
    }
    sc.close();


    long[][] dp = new long[N][N];
    dp[0][0] = 1;

    System.out.println(Jump(dp, map));
  }
}

 

 

 

 

Reference
https://velog.io/@qwerty1434/%EB%B0%B1%EC%A4%80-1890%EB%B2%88-%EC%A0%90%ED%94%84