백준 1937번 욕심쟁이 판다

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

1937번: 욕심쟁이 판다

dfs문제. 엄청 쉽게 생각해서 그냥 풀었더니 시간 초과가 나서 dp 이용해서 풀었다. 역시 그냥풀리면 골드3이 아니지..

1. 판다는 주변에 나무가 더 많은 곳으로 이동, 며칠 갈 수 있는가? 를 묻는 문제
2. dfs로 탐색 -> 시간초과
3. 이미 지나온 곳은 어디서 접근하든 결과가 같으므로 테이블에 현재 위치 = 다음 위치 + 1 개만큼 더 갔다는 걸 떠올려서 dp테이블 만들기 (안지나 간 곳?->탐색    이미지 나간 곳? -> 테이블 가져다 쓰기
4. 통과

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

public class Main {
	static int N;
	static int [][] forest;
	static int result;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		forest = new int[N+1][N+1];
		for(int i=1;i<=N;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=1;j<=N;j++) {
				forest[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				result = Math.max(result, dfs(i,j,1));
			}
		}
		System.out.println(result);
	}
	static int dfs(int i,int j,int count) {
		int [][] next = {{-1,0},{1,0},{0,1},{0,-1}};
		int max = count;
		for(int k=0;k<4;k++) {
			int nextI = i+next[k][0];
			int nextJ = j+next[k][1];
			if(nextI == 0 || nextI>N) continue;
			if(nextJ == 0 || nextJ>N) continue;
			if(forest[i][j] >= forest[nextI][nextJ]) continue;
			max = Math.max(max, dfs(nextI,nextJ,count+1));
		}
		return max;
	}
}

이건 처음 푼 코드, 배열 하나하나당 결과를 뽑아내고 저장은 하지 않았다. (DP 없음) 

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

public class bj1937 {
	static int N;
	static int [][] forest;
	static int [][] dp; //경로 테이블
	static int result;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		forest = new int[N+1][N+1];
		dp = new int[N+1][N+1];
		for(int i=1;i<=N;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=1;j<=N;j++) {
				forest[i][j]=Integer.parseInt(st.nextToken());
			}
		}
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=N;j++) {
				result = Math.max(result, dfs(i,j));
			}
		}
		System.out.println(result);
	}
	static int dfs(int i,int j) {
		if(dp[i][j] != 0) { //이미 지나간곳 (계산완료)
			return dp[i][j];
		}
		dp[i][j] = 1;
		int [][] next = {{-1,0},{1,0},{0,1},{0,-1}};
		for(int k=0;k<4;k++) { //4방 탐색
			int nextI = i+next[k][0];
			int nextJ = j+next[k][1];
			if(nextI == 0 || nextI>N) continue; //i조건
			if(nextJ == 0 || nextJ>N) continue; //j조건
			if(forest[i][j] >= forest[nextI][nextJ]) continue; // 다음 장소가 나무가 더 적은경우
			dp[i][j] = Math.max(dp[i][j], dfs(nextI,nextJ)+1); // 지금 장소 = 다음장소 +1 개만큼 갈수있음
		}
		return dp[i][j];
	}
}

DP 사용해서 푼 코드. 사실 DP만 추가한 거라서 그렇게 큰 차이는 없다.