정의
모든 경우의 수를 찾아야 하는데 중복된 계산이 존재할 때 함께 사용한다.
현재 노드에서 진행할 수 있는 모든 경우의 수를 DFS로 탐색하고 결과를 DP 배열에 저장해 놓는다.
모든 탐색이 완료된 노드를 재방문한 경우 메모이제이션할 수 있다.
하지만 탐색이 완료되지 않았음에도 불구하고 노드를 재방문한다면 사이클이 존재한다.
사이클이 없는 DFS
ex. 목적지까지 도달하는 모든 경우의 수를 세기
bool visited[51][51];
int dp[51][51];
int dfs(int x, int y) {
if(baseCondition)
return 0;
if(dp[x][y] != -1) // 메모이제이션
return dp[x][y];
if(!visited[x][y]) {
visited[x][y] = true;
int ret = 0;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(!OOB(nx, ny)) // Out of Bounds
continue;
ret += dfs(nx, ny);
}
dp[x][y] = ret;
}
return dp[x][y];
}
사이클을 확인해야 하는 DFS
ex. 가장 깊게 이동하기
bool cycle = false;
bool visited[51][51];
int dp[51][51];
int dfs(int x, int y) {
if(cycle) return 0;
if(baseCondition)
return 0;
// DP O : 메모이제이션
if(dp[x][y] != -1)
return dp[x][y];
// 방문 O + DP X : 사이클
if(visited[x][y] && !dp[x][y] == -1) {
cycle = true;
return 0;
}
// 방문 X : 탐색 시작
if(!visited[x][y]) {
visited[x][y] = true;
int ret = 1;
for(int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if(!OOB(nx, ny)) // Out of Bounds
continue;
ret = max(ret, dfs(nx, ny) + 1);
}
dp[x][y] = ret;
}
return dp[x][y];
}
Tip.
dp 배열의 초기값은 일반적으로 -1로 하는 것이 좋다.
모든 곳을 탐색했는데도 값이 0일 수가 있기 때문이다.
그러면 모든 탐색이 완료된 값이 0인 곳을 방문할 때, 메모이제이션을 할 수 있게 된다.
백준 추천 문제