[코드카타] 완전탐색 - 피로도 - 백트래킹 vs. std::next_permutation

 

프로그래머스

위 문제 풀이를 하며 떠올린 방식은 백트래킹.

- 재귀적으로 하위 분기에 대한 답을 구해나간다.

- 현재 분기에 대한 유효성 판단을 하고 유효하지 않은 경우 더 깊이 내려가지 않는다. (가지치기 pruning)

- 재귀 호출 이후 현재 상태를 다시 원상복구 시켜준다.

해당 문제에 적용한다면,

- 재귀 함수는 반복문 안에서 모든 던전에 대해 아래를 수행한다.

- 가지치기 : 탐색 가능한지 조건 체크 --> 피로도가 충분한지 & 이미 탐색하지는 않았는지

- 현재 던전 탐색 --> 피로도, 방문 여부, 탐색한 던전 수 업데이트

- 다음 던전에 대한 재귀 호출

- 재귀 호출 종료 시 --> 피로도, 방문 여부, 탐색한 던전 수 복원

- 반복문 종료 시 탐색한 던전 수 최대값 업데이트

 

또 한가지 떠올린 방식은 std::next_permutation 을 활용하는 것이었다.

- 가능한 모든 던전의 순열을 구한다.

- 각 순열 내 던전을 순서대로 방문할 때 탐색 가능한 횟수를 체크

- 최대값 반환

우선 그나마 이해하기 쉽다고 생각한 백트래킹으로 코드를 작성했다.

 

#include <vector>
#include <algorithm>

using namespace std;

void explore(int k, const vector<vector<int>>& dungeons, vector<bool>& explored, int& count, int& max) {
    for (int i = 0; i < dungeons.size(); ++i) {
        // skip if dungeon i is already explored or k is insufficient
        if (explored[i] || dungeons[i][0] > k) continue;
        
        // explore dungeon i
        k -= dungeons[i][1];
        explored[i] = true;
        count++;
        
        // recursion to explore further
        explore(k, dungeons, explored, count, max);
        
        // reset current iteration for the next dungeon
        k += dungeons[i][1];
        explored[i] = false;
        count--;
    }
    // update max if the count of explored dungeons is greater than max
    if (count > max) max = count;
}

int solution(int k, vector<vector<int>> dungeons) {
    /* 1. Backtracking */
    vector<bool> explored(dungeons.size());
    int max = 0;
    int count = 0;
    explore(k, dungeons, explored, count, max);
    
    return max;
}

(알고리즘 공부하면 가끔 괜히 어려워보이는 단어를 갖다 붙인다는 느낌이 든다... ㅎ... 그냥 조건 체크한 건데 '가지치기' 까아쥐~)

 

핵심은

1. 재귀함수 내에서 if 조건문으로 '유망'하지 않은 분기는 탐색하지 않는 것.

- 해당 문제에서는 이미 탐색했는지, 피로도가 충분한지를 체크한다.

2. 재귀 호출 이후 상태를 복원하는 것

- 재귀 호출 이전 변경한 피로도, 탐색 여부, 탐색 카운트를 복구한다.

 

이후 next_permutation 을 이용한 풀이도 한 번 돌려보았다.

/* 2. using std::next_permutation */
    int max = 0;
    sort(dungeons.begin(), dungeons.end());
    do {
        int currK = k;
        int count = 0;
        for (int i = 0; i < dungeons.size(); ++i)
        {
            if (currK < dungeons.at(i).at(0)) continue;
            count++;
            currK -= dungeons.at(i).at(1);
        }
        if (count > max) max = count;
    } while (next_permutation(dungeons.begin(), dungeons.end()));
    
    return max;

 

장점 : 탐색 여부를 추적하지 않아도 되기에 벡터 하나를 통째로 삭제 가능하다...

장점2 : 무지 간결하다.

 

그렇다면 시간이 얼마나 걸렸는지 비교해보자.

왼쪽 : 백트래킹 / 오른쪽 : next_permutation

 

테스트 1~6 : 0.01~0.02ms 차이라 미미하다. 

테스트 7 : 백트래킹이 확실하게 더 빠르다. 0.23ms 차이

테스트 8 : next_permutation 이 확실하게 더 빠르다. 0.33ms 차이

테스트 9~19 : 동일한 경우를 제외하면 백트래킹이 확실하게 더 빠르다. 각각 0.04, 0.38, 0.78, 0.81, 0.81, 0.09, 0.83ms 차이

 

8개 테스트에서 백트래킹이 더 빨랐다. next_permutation 이 더 빠른 테스트는 8번 1개뿐.

next_permutation 이 매 iteration 실행되기에 그런 것이겠지.

재귀 호출은 모든 경우의 수에 대해 다 호출되지만 if 체크가 빠르게 빠르게 iteration 을 치워버리니까...

 

+

DFS 와의 차이?

- DFS depth-first search 는 맨 마지막까지 도달할 때까지 무조건 탐색한다.

- 백트래킹은 현재 지점이 유망하지 않은 경우 더 하위 분기로 내려가지 않고 이전 지점으로 돌아간다.