[백준] 1937번 욕심쟁이 판다 자바

문제

 

1937번: 욕심쟁이 판다

 

 

문제 풀이

 

dfs와 dp의 조합..! 처음에 dp생각 못하고 dfs로만 모든 경우 구하면서 max값 갱신하다가 시간초과가 떴다.

왜 dp를 생각못했을까..ㅠ int[][] visited 배열 하나 선언해두고, 해당 칸에서 갈 수 있는 길이를 저장해둠으로써 좀 더 효율적인 로직을 만들 수 있다.

 

✔️dfs 알고리즘

1. 해당 칸 방문이 되었으면 그 값 바로 리턴

2. 그렇지 않으면 1로 초기화 후, 상하좌우로 이동하면서 현재 값을 최대로 갱신한다.

3. 아예 움직일 수 있는 곳이 없으면 for문이 안 도므로 바로 초기화했던 1이 리턴된다.

 

 

소스 코드

 

public class 욕심쟁이판다 {

	static int n;
	static int[][] map;
	static int[][] dp;
	static int[] dr = {-1, 1, 0, 0};	//상하좌우
	static int[] dc = {0, 0, -1, 1};
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int ans = 0;
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		dp = new int[n][n];
		
		for(int i = 0; i < n; i++) {
			String[] str = br.readLine().split(" ");
			for(int j = 0; j < n; j++)
				map[i][j] = Integer.parseInt(str[j]);
		}
	
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < n; j++) {
				int cur = dfs(i, j);
				ans = cur > ans ? cur : ans;
			}
		}
		
		System.out.println(ans);
		br.close();
	}
	
	public static int dfs(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 nextR = r + dr[i];		//다음으로 움직일 좌표
			int nextC = c + dc[i];	
			
			//격자 범위 내이고, 다음 칸의 수가 더 커서 이동할 수 있는 경우
			if(nextR >= 0 && nextR < n && nextC >= 0 && nextC < n) {
				if(map[nextR][nextC] > map[r][c])
					dp[r][c] = Math.max(dp[r][c], dfs(nextR, nextC) + 1);
			}
		}
		
		return dp[r][c];
	}

}