문제
n이 주어지고 n * n 으로 이루어진 숫자들의 배열이 주어진다.
시작점에서 본인보다 큰 수로만 이동이 가능 할 때, 최대로 이동할 수 있는 거리를 구하여라.
문제 풀이 방법
- 처음에는 dp + bfs로 풀이하려다가 메모리 초과 발생
- dp를 찾는 함수를 구해서 풀이하려다가 원하는 답이 나오지 않음
오답 풀이
public static int findDP(int x, int y){
if (dp[x][y] > -1)
return dp[x][y];
dp[x][y] = 1;
int origin = grid[x][y];
for (int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if (inRange(nx, ny)){
int forCheck = grid[nx][ny];
if (origin < forCheck)
dp[x][y] = Math.max(dp[x][y], dp[nx][ny] + 1);
}
}
return dp[x][y];
}- 여기서는 dp의 값이 원하는 값이 나오지 않음
맞는 풀이
public static int findDP(int x, int y){
if (dp[x][y] > -1)
return dp[x][y];
dp[x][y] = 1;
int origin = grid[x][y];
for (int i = 0; i < 4; i++){
int nx = x + dx[i];
int ny = y + dy[i];
if (inRange(nx, ny)){
int forCheck = grid[nx][ny];
if (origin < forCheck)
dp[x][y] = Math.max(dp[x][y], findDP(nx, ny) + 1);
}
}
return dp[x][y];
}- 차이는
dp[x][[y] = Math.max()부분이다.
max 값을 구할 때,findDP(nx, ny)로 함수를 통해 dp값을 찾는 것과
dp[nx][ny]로 입력된 dp값을 찾는 것이다.
🔥 차이점 요약
| 항목 | 처음 코드 (findDP) | 지금 코드 (findDP with DFS) |
|---|---|---|
| 계산 순서 | 무조건 (0,0)부터 순서대로 | 필요한 곳만 재귀적으로 계산 |
| dp[x][y] 갱신 | 옆 칸을 참조해서 갱신하려고 시도함 | 옆 칸을 먼저 계산하고 나서 그 값을 사용 |
| 의존 순서 보장 | ❌ 안 됨 (dp[nx][ny]가 아직 1일 수도 있음) | ✅ 재귀니까 항상 dp[nx][ny] 먼저 계산됨 |
| 동작 정확성 | 데이터에 따라 정답이 나오기도, 틀리기도 함 | 항상 정확히 동작함 |
| 계산 방식 | 반복문 순회 + 조건문 안에 수식 | DFS + 메모이제이션 구조 |
메모리제이션
계산 했던 값은 다시 계산하지 않도록 저장하는 것!
public static int findDP(int x, int y){
if (dp[x][y] > -1) // 초기 설정 값이 아니면
return dp[x][y]; // 계산 한 값을 리턴!