(중요x99999) DFS 최적화와 구현 방식

1. DFS + DP 최적화

 

DFS를 당연히 DP로 최적화 할 수 있다

이미 탐색을 해본 곳이면 DP값만 불러오면 되기 때문이다

int dfs(int y, int x){

    // 종점 도달했으면
    if(y == N-1 && x == M-1){
        return 1;
    }

    // 이미 계산이 되어있다면
    if(dp[y][x]!=-1){
        return dp[y][x];
    }

    int sum = 0;
    int newy, newx;
    for (int i = 0; i < 4; i++)
    {
        newy = y + dy[i];
        newx = x + dx[i];

        if (newy < 0 || newx < 0 || newy >= N || newx >= M)
            continue;

        // 답이 없는 루트로 계산되었으면 무시
        // 경로가 없는 경우까지 최적화
        if(dp[newy][newx] == 0)
            continue;

        // 항상 더 작을때만 이동
        if (map[y][x] > map[newy][newx])
        {
            sum += dfs(newy,newx);
        }
    }

    dp[y][x] = sum;

    return sum;
}

 

아래는 DFS + DP 최적화 연습하기 좋은 문제

 

https://www.acmicpc.net/problem/1520

 

---

2. 재귀 vs 스택 ?

 

오랜만에 DFS와 백트래킹을 풀다 나온 고민인데 해결이 되었다.

 

DFS와 백트래킹은 그냥 순수 재귀함수로 구현이 가능하고 내부적으로 stack을 써서 돌릴 수도 있는데

사실 재귀호출로 쓰는게 가장 직관적인 방식이다. 가장 먼저 떠오름.

 

근데 stack을 쓰면 공간복잡도가 몇배로 줄어든다.

 

그래서 든 생각이 그럼 상위티어로 가면 stack으로 구현안하고 재귀로 구현했을때

시간초과나 메모리초과가 일어나는 경우가 있을까? 라는 것이었다

 

만약 일어나는 경우가 있으면 재귀로 떠올린 방식을 stack으로 변형해서 풀어야하는데

이 과정이 시간을 겁나 잡아먹는다.

 

원래 순서가 재귀로 생각하고 이걸 반복문 + stack으로 구현하는거니까

 

근데 극상위티어 문제에서도 stack으로 안했다고 틀렸습니다 뜨는 경우는 없다고 한다

 

그래서 결론은 그냥 재귀로만 밀고 가도 된다

 

다만 파이썬이나 자바를 쓰면 종종 뜬다고 한다.

역시 c++이 개꿀이다.