[DFS/백트래킹]DFS와 백트래킹의 차이점

DFS와 백트래킹의 차이점

 

 

BFS/DFS를 공부할때, DFS는 트리의 특정 노드의 깊이 순서대로 방문하고 방문한 노드의 깊이가 최대 깊이일시 부모 노드로 올라가는 형식으로 작업된다.

 

이는 백트래킹 알고리즘의 조건에 만족하지 않으면 되돌아가는 성격과 유사하다고 판단되었다.

하지만 둘을 동일하게 STACK을 사용하여 구현시 달랐다.

 

어떤부분에서 차이가 있고 같은것일까?

 

1. DFS

개념

• DFS는 그래프 탐색 알고리즘으로, 한 경로를 따라 가능한 깊이까지 탐색한 후, 다른 경로를 탐색하는 방식.
• 기본적으로 모든 경로를 탐색하며, 최단 거리나 최적해를 구하는 것이 아니라 단순히 모든 노드에 방문하는 것이 주된 목표.

특징

• 완전탐색 방법론의 하나로, 모든 가능성을 고려.
• 최적화 없이, 모든 가능한 경우를 다 시도.
• 주로 재귀 호출 또는 스택을 이용해 구현.
• 목적: 그래프의 특정 요소(노드, 경로)를 탐색하거나 찾는 데 사용

예시

그래프에서 특정 노드를 방문하거나, 경로를 찾기 위해 DFS를 사용.

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    for (int next : graph[node]) {
        if (!visited[next]) {
            dfs(next, graph, visited);
        }
    }
}

2. 백트래킹

개념

• 백트래킹은 제약 조건을 만족하는 해를 찾기 위한 알고리즘으로, DFS의 변형 또는 확장된 개념으로 볼 수 있음.
• 탐색 도중 **유망하지 않은 경로(불필요한 탐색 경로)**를 빠르게 제외(가지치기)하여 효율적으로 탐색.

특징

• DFS와 달리, 유망하지 않은 경로를 탐색하지 않음으로써 연산을 줄이는 것이 목표.
• 가지치기(Pruning)를 통해 탐색 속도를 크게 향상.
• 최적해를 찾는 데 주로 사용.
• 주로 조합, 순열, 경로 찾기 문제 등 최적화 문제나 제약 조건이 있는 탐색 문제에 적합.

예시

N-Queens 문제에서, 현재 놓여 있는 퀸들이 서로 공격하지 않는다는 조건을 만족하지 않으면 해당 경로를 더 이상 탐색하지 않음.

bool isSafe(vector<int>& board, int row, int col) {
    for (int i = 0; i < row; ++i) {
        if (board[i] == col || abs(board[i] - col) == row - i) {
            return false; // 같은 열이나 대각선에 퀸이 있음
        }
    }
    return true;
}

void solveNQueens(int row, int n, vector<int>& board, vector<vector<int>>& results) {
    if (row == n) {
        results.push_back(board); // 모든 퀸을 배치한 경우
        return;
    }

    for (int col = 0; col < n; ++col) {
        if (isSafe(board, row, col)) { // 조건을 만족하는 경우만 탐색
            board[row] = col;
            solveNQueens(row + 1, n, board, results);
            board[row] = -1; // 백트래킹
        }
    }
}

 

-> 결국 차이는 백트래킹은 최적의 해가 존재함. ( 최적의 해란 트리구조의 루트 -> 마지막 노드까지가 완성되는것 )

BFS는 최적의 해가 존재하지 않고, 연결되어있는 모든 노드를 방문하는것이 목적.

어떻게 방문하던 순서는 상관이 없음.