[백준 1937] 욕심쟁이 판다 - JAVA

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

 

 

이전 문제랑 거의 똑같다.

https://sh3542.tistory.com/251

[백준 1520] 내리막 길 - JAVA

 

dp[r][c] = 1은

 

지역을 방문했다는 것은 그 지역의  대나무를 먹었다는 뜻이기에 +1 하는 의미도 있고,

방문하지 않았음 (dr[r][c] = 0)일 때 와 구분하는 역할도 한다. 처음부터 배열을 1로 채우면 불필요한 탐색이 추가되므로 시간초과를 받는다.

 

특이한 점은,

m[tr][tc] < m[r][c]

 

조건의 부등호를 >로 바꿔도 ac다.

 

어차피 배열의 모든 부분을 탐색하며,

 

1. (i,j)를 시작점으로 한다 -> 더 큰 대나무가 있으면 이동하며 임의의 도착 지점을 찾는다.

2. (i,j)를 도착점으로 한다 -> 임의의 도착 지점에서 더 작은 대나무가 있으면 이동하며 (i,j)를 찾는다.

 

둘 다 말이 되기 때문이다.

 

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

class Main {

  static int solve(int r, int c) {

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

    dp[r][c] = 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 < N && m[tr][tc] < m[r][c]) {
        dp[r][c] = Math.max(solve(tr, tc) + 1, dp[r][c]);
      }
    }

    return dp[r][c];
  }

  static int N, 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());

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

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

    int ans = 0;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        ans = Math.max(solve(i, j), ans);
      }
    }
    System.out.println(ans);
  }
}