백준 1937 - 욕심쟁이 판다

[문제 바로가기]

 

1. 유형

DFS, 메모리제이션

 

2. 문제 접근

 

처음으로 든 풀이법은 배열을 완전탐색하면서 DFS를 한번씩 사용하는 것 입니다. 

하지만 이러면 500^4의 시간이 걸리기 때문에 시간초과가 날 것입니다.

 

따라서 이 문제에선 DFS+DP를 써야됩니다.

9	10
1	11

위와 같은 원본 테이블이 있습니다. 최대 길이는 1->9->10->11으로 4가 나옵니다.

DP[r][c] = val

val은 현재 좌표에서 최대 길이를 의미. DP테이블을 구해봅시다.

 

그림1

그림1은 DP테이블 초기화.

(0,0)에서 DFS를 한번 돌립니다. 

그림2

그럼 그림2와 같은 테이블이 될것입니다.

그 다음 (1,0)에서도 DFS를 돌려야 할까요? 아닙니다.

(1,0)에서 4방향을 탐색합니다. 원본배열에서 1 < 9 이니깐, 본인보다 더 큰 것을 확인 -> DP에 저장된 값을 받아옴.

그림3

최종적으로 그림3 같은 테이블이 완성.

 

재귀의 리턴값을 이용할 수 있는 구현력과 메모리제이션을 써야된다는 아이디어가 필요한 문제였습니다.

 

3. 코드

import java.io.*;
import java.util.*;

public class Main {
	static int N, matrix[][], d[][]= {{-1,0},{0,1},{1,0},{0,-1}};
	static int v[][];
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		matrix = new int[N][N];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine());
			for (int j = 0; j < N; j++) {
				matrix[i][j]= stoi(st.nextToken());
			}
		}
		v=new int[N][N];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if(v[i][j]==0) {
					dfs(i,j);
				}
			}
		}
		int answer =0;
		for(int i=0; i<N; i++)
			answer = Math.max(answer, Arrays.stream(v[i]).max().getAsInt());
		System.out.println(answer);
	}
	static int dfs(int r, int c) {
		int max=0;
		for(int k=0; k<4; k++) {
			int nr = r+d[k][0];
			int nc = c+d[k][1];
			if(nr<0||nr>=N||nc<0||nc>=N || matrix[nr][nc]<=matrix[r][c]) continue;
			if(v[nr][nc]!=0) {
				max = Math.max(max, v[nr][nc]);
				continue;
			}else if(v[nr][nc]==0)
				max = Math.max(max, dfs(nr,nc));
		}
		v[r][c] = max+1;
		return v[r][c];
	}
	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}