[알고리즘] 백 트래킹 (Back Tracking)

[알고리즘] 백 트래킹 (Back Tracking)

Tags

Algorithm

백트래킹 (Back Tracking)

개념

백트래킹은 알고리즘 기법 중 하나로, 문제를 재귀로 풀어가면서 조건에 위배되거나 해가 될 가능성이 없는 경로는 더이상 탐색하지 않고 되돌아간다.

구현

탐색 중 특정 조건을 만족하지 않으면 이전 경로로 되돌아가 다른 경로를 탐색.

경로를 추적하기 위해 스택을 사용해 현재 탐색 중인 경로를 명시적으로 저장하고 관리.

실습

BFS 백트래킹


void dfs(vector<vector<int>>& graph, int node, vector<bool>& visited, vector<int>& path) {
    visited[node] = true;
    path.push_back(node); // 경로를 명시하기 위해 사용

    for (int i : graph[node]) {
        if (!visited[i]) {
            dfs(graph, i, visited, path);
        }
    }
    
    path.pop_back(); // 경로를 명시하기 위해 사용
    visited[node] = false;
}