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

 

---

 

• 생각

1. 모든 index를 bfs 메소드로 보내서 가장 긴 max 값을 찾는다 => 시간초과 뜰 것 같다. X

 

2. dp 배열을 통해 지나온 길은 최장길이가 몇인지 저장해둔다 => 전에 저장되있는 길에 지금 까지 왔던 길이 걸릴 수 있다? => 대나무 개수가 지나온 길은 안걸리게 해줌(그 전 대나무 개수가 더 많아야 되기 때문) => dfs 이용 O

 

 

• 코드

정답 코드 : dfs로 배열을 정확하게 돌아주고, dp배열을 통해 시간을 단축시킨다.

 

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

public class Main {
	static int n;
	static int[][] array, dp;
	static int[] x = { -1, 1, 0, 0 };
	static int[] y = { 0, 0, -1, 1 };

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;

		n = Integer.parseInt(br.readLine());
		array = new int[n][n];
		dp = new int[n][n];

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

        int max = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                max = Math.max(dfs(i, j), max);
            }
        }
        System.out.println(max);
    }
 
    static int dfs(int i, int j) {
        // basecase 기존에 저장되있는 dp 값을 return
    	if(dp[i][j] != 0) {
            return dp[i][j];
        }
        
        int count = 1;
        for (int direction = 0; direction < 4; direction++) {
			int r = i + x[direction];
			int c = j + y[direction];
			
            if(r >= 0 && r < n && c >= 0 && c < n) {
                if(array[i][j] < array[r][c]) {
                    count = Math.max(dfs(r, c) + 1, count);
                    // 가장 큰 count 값을 dp에 저장
                    dp[i][j] = count;
                }
            }
        }
        return count;
    }
}