문제풀이/백준
[백준]1937: 욕심쟁이 판다 -JAVA
빈둥벤둥
2021. 2. 21. 15:02
[백준]1937: 욕심쟁이 판다
1937번: 욕심쟁이 판다
n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서
www.acmicpc.net
풀이
처음에는 DFS만 사용해서 풀었더니 시간초과가 났다! DP와 DFS를사용해 메모이제이션 하면서 풀어야 한다.
dp에 저장되는 값은 다른 위치에서 현재 위치까지 이동할 수 있는 거리 중 최대값을 의미한다. 그러므로 이동하면서 계속 갱신해 주어야 한다.
즉 현재위치가 x, y이고 이동할 위치가 nx, ny라고 할 때
dp[x][y] = dp[nx][ny] + 1과 dp[x][y]중의 최댓값이 된다.
코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
import java.util.*;
public class Main {
static int[] dx = {0, 1, 0, -1};
static int[] dy = {-1, 0, 1, 0};
static int max = 0;
static int[][] node;
static int[][] dp;
static int n;
public static void main(String[] args) throws Exception {
Scanner scan = new Scanner(System.in);
n = scan.nextInt();
node = new int[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
node[i][j] = scan.nextInt();
}
}
dp = new int[n][n];
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);
}
public 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 && ny >= 0 && nx < n && ny < n) {
if(node[nx][ny] > node[x][y]) {
dp[x][y] = Math.max(dp[x][y], dfs(nx, ny) + 1);
}
}
}
return dp[x][y];
}
}
|
cs |