백트래킹

b4failrise ㅣ 2021. 9. 16. 10:57

  • 제약 조건을 만족하는 문제를 해결하기 위해 쓰는 알고리즘
  • 특정 조건을 만족하는 조합 알고리즘에 해당하는 모든 해를 찾는 문제 (모든 경우의 수 중 조건에 위배되는 경우는 빼고 답을 찾는 것)
  • 답이 될 수 있는 모든 경우의 수를 DFS를 이용해 찾음
    만약 답이 될 수 없는 경우면 더 이상 탐색하지 않고 이전으로 돌아감
  • 재귀로 푸니까 스택 메모리 제한 확인해야됨
  • 시간복잡도 O(N!) 개 오 래 걸 림 (N이 클 경우 백트래킹을 적용하면 시간초과 남)
    12! = 479001600 = 4*10^8

기본 틀

void backtracking(int cnt, int idx) {
    if (cnt == m) {
        //조건 만족시 해야될 일 적음
        return;
    }
    for (int i = idx; i < n; i++) {
        if (!visited[i]) {
            visited[i] = true; //상태변화
            backtracking(cnt + 1, i); 
            visited[i] = false; //원상복구
        }
    }
}

백트래킹 코드는 이 틀 내에서 문제에 따라 적절히 응용해야함
인덱스 설정이나 탈출 조건은 문제에 따라 바꿔주면 되고
상태변화 & 원상복구가 중요함 원래대로 복구하는거 빼먹지 않도록 주의

레퍼런스

'자료구조 & 알고리즘' 카테고리의 다른 글

0. 정렬 알고리즘 장단점, 수행시간 비교, 속도 비교, 종류  (0) 2021.09.16
탐색 알고리즘  (0) 2021.09.16
시간 복잡도 차트  (0) 2021.09.16
스택  (0) 2021.08.20