[백준 1520] 내리막 길 - JAVA

https://www.acmicpc.net/problem/1520

 

두 코드를 비교했을 때,

재귀적으로 경로를 찾아가는 것은 동일하다.

다만, 방문처리 (코드에선 -1 or 0)을 하지 않으면 불필요한 재귀가 반복되어 시간초과였다.

 

AC

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
  static int solve(int r, int c) {

    if (dp[r][c] != -1) {
      return dp[r][c];
    }

    if (r == 0 && c == 0) return 1;

    dp[r][c] = 0;

    for (int i = 0; i < 4; i++) {
      int tr = r + dr[i];
      int tc = c + dc[i];

      if (tr >= 0 && tr < N && tc >= 0 && tc < M && m[tr][tc] > m[r][c]) {
        dp[r][c] += solve(tr, tc);
      }
    }

    return dp[r][c];
  }

  static int N, M, dp[][], m[][], dr[] = {0, 0, -1, 1}, dc[] = {-1, 1, 0, 0};

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());

    dp = new int[N][M];
    m = new int[N][M];

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < M; j++) {
        m[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    for (int i = 0; i < N; i++) {
      Arrays.fill(dp[i], -1);
    }

    System.out.println(solve(N - 1, M - 1));
  }
}

 

 

WA (시간초과)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Main {
  static int solve(int r, int c) {

    if (dp[r][c] != 0) {
      return dp[r][c];
    }

    if (r == 0 && c == 0) return 1;

    for (int i = 0; i < 4; i++) {
      int tr = r + dr[i];
      int tc = c + dc[i];

      if (tr >= 0 && tr < N && tc >= 0 && tc < M && m[tr][tc] > m[r][c]) {
        dp[r][c] += solve(tr, tc);
      }
    }

    return dp[r][c];
  }

  static int N, M, dp[][], m[][], dr[] = {0, 0, -1, 1}, dc[] = {-1, 1, 0, 0};

  public static void main(String[] args) throws IOException {

    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());

    dp = new int[N][M];
    m = new int[N][M];

    for (int i = 0; i < N; i++) {
      st = new StringTokenizer(br.readLine());
      for (int j = 0; j < M; j++) {
        m[i][j] = Integer.parseInt(st.nextToken());
      }
    }

    System.out.println(solve(N - 1, M - 1));
  }
}