
https://www.acmicpc.net/problem/1937
문제분석
판다가 갈 수 있는 '가장 긴 거리' 를 알아내는 문제이다. 핵심은 dp를 "얼마나 더 갈 수 있는지 저장" 하는 것이다. 문제를 보면 알겠지만, 모든 칸에서 DFS를 돌아야 한다. 따라서, 가지치기를 통해 DFS횟수를 최소화 하는 것이 가장 중요하다.
처음에는 깊이(depth)를 파악하려고 했다. 하지만 이렇게 된다면 DFS를 최소화하지 못하고, 시간초과로 틀리게 된다.
따라서, DFS를 할 때 dp에 값이 없으면, 모든 방향 DFS를 돌고 그중 최고값을 저장하게 끔 해야한다.
쉽게말해, "애매하게 여러 번 보다, 확실하게 한번" 계산하자는 게 이 문제의 목적이다.
코드
import java.util.*;
import java.io.*;
public class Main {
static int[][] map;
static int[][] dp;
static int[] dr = { -1, 0, 1, 0 };
static int[] dc = { 0, -1, 0, 1 };
static int max = Integer.MIN_VALUE;
static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
map = new int[n][n];
dp = new int[n][n];
StringTokenizer st;
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < n; j++) {
int input = Integer.parseInt(st.nextToken());
map[i][j] = input;
dp[i][j] = 0;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = DFS(i, j);
}
}
System.out.println(max);
}
static int DFS(int r, int c) {
if (dp[r][c] != 0) { // dp값이 저장된 게 있는 경우 해당 값 반환.
return dp[r][c];
} else {
int t = 0;
for (int i = 0; i < 4; i++) {
int nr = r + dr[i];
int nc = c + dc[i];
if (nr >= 0 && nc >= 0 && nr < n && nc < n && map[r][c] > map[nr][nc]) {
t = Math.max(t, DFS(nr, nc));
}
}
dp[r][c] = t + 1;
max = Math.max(dp[r][c], max);
return dp[r][c];
}
}
}

'알고리즘&PS > PS' 카테고리의 다른 글
| [JAVA] 백준 1520 내리막 길 (0) | 2026.03.06 |
|---|---|
| [JAVA] 백준 2293 동전 1 (0) | 2026.03.06 |
| [JAVA] 백준 11000 회의실 배정 (0) | 2026.03.06 |
| [JAVA] 백준 15683 감시 (0) | 2026.03.05 |
| [JAVA] 백준 16928 뱀과 사다리 게임 (0) | 2026.03.05 |