탐색 알고리즘의 기본 구조와 차이점

탐색 알고리즘은 문제 해결의 핵심 도구로, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)은 기본적이면서도 중요한 역할을 합니다. 두 알고리즘의 차이는 단순히 탐색 순서만이 아닌, 내부 동작 방식과 최적화 가능성에서 뚜렷하게 나타납니다.

DFS와 BFS의 동작 원리 비교

DFS는 스택 구조를 활용하여 경로의 깊이를 우선적으로 탐색합니다. 반면 BFS는 큐를 사용하여 계층별로 확장하는 방식으로 동작합니다.

• DFS: 경로 구성, 연결성 판단에 적합
• BFS: 최소 단계, 최적 해 탐색에 효과적

이진 트리 탐색 구현 예제

// DFS: 재귀를 이용한 전위 순회
void depthFirstSearch(TreeNode* node) {
    if (node == nullptr) return;
    cout << node->value << endl;
    depthFirstSearch(node->leftChild);
    depthFirstSearch(node->rightChild);
}

// BFS: 큐를 활용한 레벨 순회
void breadthFirstSearch(TreeNode* root) {
    if (root == nullptr) return;
    queue<TreeNode*> nodeQueue;
    nodeQueue.push(root);
    
    while (!nodeQueue.empty()) {
        TreeNode* current = nodeQueue.front();
        nodeQueue.pop();
        cout << current->value << endl;
        
        if (current->leftChild != nullptr)
            nodeQueue.push(current->leftChild);
        if (current->rightChild != nullptr)
            nodeQueue.push(current->rightChild);
    }
}

알고리즘 특성 비교표

DFS 최적화 기법

가지치기 기법

조합 문제에서 DFS의 효율을 높이기 위해 가지치기를 적용합니다. 현재 경로가 유효한 해를 생성할 수 없는 경우 조기에 탐색을 중단합니다.

vector<vector<int>> findCombinations(vector<int>& numbers, int target) {
    vector<vector<int>> results;
    sort(numbers.begin(), numbers.end());
    
    function<void(int, vector<int>&, int)> search = [&](int index, vector<int>& path, int remaining) {
        if (remaining == 0) {
            results.push_back(path);
            return;
        }
        for (int i = index; i < numbers.size(); i++) {
            if (numbers[i] > remaining) break;
            path.push_back(numbers[i]);
            search(i, path, remaining - numbers[i]);
            path.pop_back();
        }
    };
    
    vector<int> temp;
    search(0, temp, target);
    return results;
}

메모이제이션을 활용한 최적화

중복 계산을 피하기 위해 상태를 저장하는 메모이제이션 기법을 적용합니다.

int findMinPath(vector<vector<int>>& matrix, int row, int col, unordered_map<string, int>& memory) {
    string key = to_string(row) + "," + to_string(col);
    if (memory.count(key)) return memory[key];
    
    if (row == matrix.size()-1 && col == matrix[0].size()-1)
        return matrix[row][col];
    
    if (row >= matrix.size() || col >= matrix[0].size())
        return INT_MAX;
    
    int right = findMinPath(matrix, row, col+1, memory);
    int down = findMinPath(matrix, row+1, col, memory);
    
    return memory[key] = matrix[row][col] + min(right, down);
}

BFS 최적화 기법

양방향 BFS 구현

시작점과 도착점에서 동시에 탐색을 진행하여 효율성을 높입니다.

bool bidirectionalBFS(unordered_map<int, vector<int>>& graph, int start, int end) {
    if (start == end) return true;
    
    unordered_set<int> frontVisited{start}, backVisited{end};
    queue<int> frontQueue, backQueue;
    frontQueue.push(start);
    backQueue.push(end);
    
    while (!frontQueue.empty() && !backQueue.empty()) {
        if (frontQueue.size() <= backQueue.size()) {
            int current = frontQueue.front();
            frontQueue.pop();
            
            for (int neighbor : graph[current]) {
                if (backVisited.count(neighbor)) return true;
                if (!frontVisited.count(neighbor)) {
                    frontVisited.insert(neighbor);
                    frontQueue.push(neighbor);
                }
            }
        } else {
            int current = backQueue.front();
            backQueue.pop();
            
            for (int neighbor : graph[current]) {
                if (frontVisited.count(neighbor)) return true;
                if (!backVisited.count(neighbor)) {
                    backVisited.insert(neighbor);
                    backQueue.push(neighbor);
                }
            }
        }
    }
    return false;
}

다중 출발점 BFS

여러 시작점에서 동시에 탐색을 시작하여 최단 경로를 찾습니다.

int multiSourceBFS(vector<vector<int>>& grid, vector<pair<int,int>>& starts) {
    queue<pair<int,int>> positionQueue;
    vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
    
    for (auto& start : starts) {
        positionQueue.push(start);
        visited[start.first][start.second] = true;
    }
    
    vector<pair<int,int>> directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
    int steps = 0;
    
    while (!positionQueue.empty()) {
        int levelSize = positionQueue.size();
        for (int i = 0; i < levelSize; i++) {
            auto [x, y] = positionQueue.front();
            positionQueue.pop();
            
            if (grid[x][y] == 2) return steps;
            
            for (auto& dir : directions) {
                int nx = x + dir.first, ny = y + dir.second;
                if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() 
                    && !visited[nx][ny] && grid[nx][ny] != 1) {
                    visited[nx][ny] = true;
                    positionQueue.push({nx, ny});
                }
            }
        }
        steps++;
    }
    return -1;
}

A* 알고리즘 구현

휴리스틱 함수를 활용한 최적 경로 탐색 알고리즘입니다.

int manhattanDistance(pair<int,int> a, pair<int,int> b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}

vector<pair<int,int>> aStarSearch(vector<vector<bool>>& grid, pair<int,int> start, pair<int,int> goal) {
    priority_queue<tuple<int, int, pair<int,int>>, 
                   vector<tuple<int, int, pair<int,int>>>,
                   greater<tuple<int, int, pair<int,int>>>> openSet;
    
    unordered_map<pair<int,int>, pair<int,int>> cameFrom;
    unordered_map<pair<int,int>, int> gScore;
    
    gScore[start] = 0;
    openSet.push({manhattanDistance(start, goal), 0, start});
    
    while (!openSet.empty()) {
        auto [f, g, current] = openSet.top();
        openSet.pop();
        
        if (current == goal) break;
        
        for (auto& dir : vector<pair<int,int>>{{0,1}, {1,0}, {0,-1}, {-1,0}}) {
            pair<int,int> neighbor = {current.first + dir.first, current.second + dir.second};
            
            if (neighbor.first >= 0 && neighbor.first < grid.size() 
                && neighbor.second >= 0 && neighbor.second < grid[0].size() 
                && !grid[neighbor.first][neighbor.second]) {
                
                int tentativeG = g + 1;
                if (!gScore.count(neighbor) || tentativeG < gScore[neighbor]) {
                    cameFrom[neighbor] = current;
                    gScore[neighbor] = tentativeG;
                    int fScore = tentativeG + manhattanDistance(neighbor, goal);
                    openSet.push({fScore, tentativeG, neighbor});
                }
            }
        }
    }
    
    vector<pair<int,int>> path;
    for (pair<int,int> node = goal; node != start; node = cameFrom[node]) {
        path.push_back(node);
    }
    path.push_back(start);
    reverse(path.begin(), path.end());
    return path;
}

비트 연산을 활용한 상태 표현

여러 상태를 하나의 정수로 압축하여 메모리 사용량을 줄이고 접근 속도를 높입니다.

class StateCompressor {
private:
    unsigned int state;
    
public:
    StateCompressor() : state(0) {}
    
    void setVisited(int node) {
        state |= (1 << node);
    }
    
    bool isVisited(int node) {
        return state & (1 << node);
    }
    
    void clearVisited(int node) {
        state &= ~(1 << node);
    }
};