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

 

 

 

만약 모든 칸에서 DFS 탐색을 한다면 매 칸에서 최대 n^2만큼 이동할 수 있다. 따라서 n^2의 칸에서 n^2 만큼의 탐색을 한다면 O(n^4) 로 시간 복잡도가 터져버릴 것이다.

따라서 DP를 이용해서 이미 DFS 를 탐색한 칸에 대해서는 값을 저장해서 탐색 횟수를 줄여야 한다.

 

dp => 해당 칸에서의 최장 경로를 저장해둔 것이다. 

즉, 다른 칸(a)에서 탐색을 하다가 이미 방문한 칸(b)을 탐색하게 된다면,

b에서 계속해서 탐색을 할 필요가 없이, b칸에 저장되어 있는 dp값을 더하기만 하면 된다.

 

dp[i][j] => 판다가 (i,j) 에서 출발할 때 최대로 이동할 수 있는 칸 수 를 의미한다.

 

 

1) 모든 칸에서 탐색 시작

 

2) DFS 탐색

상 하 좌 우를 탐색하며, 현재 칸 보다 다음칸에 더 많은 대나무가 있다면, 해당 칸으로 이동한다.

즉, 다음칸이 현재칸이 되어 dfs(nx, ny) 로 탐색을 시작하는 것이다.

=> 상하좌우 중 최장 거리 값으로 dp[x][y] 을 갱신한다.

 

만약 현재칸의 dp값이 0이아니라면? 해당 칸에 대해서 이미 DFS 탐색을 한 적이 있음을 의미한다.

따라서 dp값을 리턴해주고 탐색을 종료한다.

 

 

 

 

문제 풀이

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringBuilder sb;
	static StringTokenizer st;
	static int n, map[][], dp[][];
	static int[] dx = {1,0,-1,0};
	static int[] dy = {0,1,0,-1};

	public static void main(String[] args) throws IOException {
		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		sb = new StringBuilder();
		n = Integer.parseInt(br.readLine());
		map = 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++) {
				map[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(ans, dfs(i,j));
			}
		}
		
		System.out.println(ans);
		
	}
	
	static int dfs(int x, int y) {
		if (dp[x][y] != 0)	return dp[x][y]; // 이미 방문한 좌표라면 
		dp[x][y] = 1; 
		
		for(int i=0; i<4; i++) {
			int nx = x+dx[i];
			int ny = y+dy[i];
			// 다음칸에 더 많은 대나무가 있다면
			if (nx>=0 &&nx<n && ny>=0 && ny<n && map[x][y] < map[nx][ny]) {
				dp[x][y] = Math.max(dp[x][y], dfs(nx,ny)+1);
			}
		}
		
		return dp[x][y];
	}
	
	
}