[DFS&BFS] DFS vs BFS 차이

ChatGPT saying…

DFS(Depth-First Search)와 BFS(Breadth-First Search)는 그래프 탐색 알고리즘으로, 각기 다른 방식으로 노드를 방문합니다. 두 가지 방법의 작동 원리와 이를 사용한 예제를 설명하겠습니다.

DFS (Depth-First Search) - 깊이 우선 탐색

DFS는 가능한 한 깊게 노드를 탐색한 후, 더 이상 깊이 탐색할 수 없으면 이전 노드로 돌아가서 다른 경로를 탐색하는 방법입니다. 주로 스택을 사용하여 구현하며, 재귀를 통해 자연스럽게 스택의 동작을 흉내낼 수 있습니다.

DFS의 작동 원리:

1. 시작 노드 선택: 시작 노드를 선택합니다.
2. 현재 노드 방문: 현재 노드를 방문하고, 해당 노드를 방문한 것으로 표시합니다.
3. 인접 노드 탐색: 현재 노드의 인접 노드 중 아직 방문하지 않은 노드를 선택하고, 그 노드로 이동합니다.
4. 재귀 호출: 인접 노드로 이동한 후, 같은 방법으로 재귀적으로 탐색을 계속합니다.
5. 백트래킹: 더 이상 탐색할 노드가 없으면, 이전 노드로 돌아가서 다른 인접 노드를 탐색합니다.

DFS의 장점:

• 경로가 깊게 있는 경우 유리합니다.
• 모든 경로를 탐색할 때 유용합니다.

DFS의 예시 (첫 번째 코드의 makeStandardShape 함수):

int makeStandardShape(int x, int y, int prev_x, int prev_y, int depth, int TetroMino[MAX][MAX], int &N, int &M){
    int answer = 0;
    if(depth == 4){
        return TetroMino[x][y];
    }
    for(int i = 0; i < 4; i++){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= N || ny >= M) {
            continue;
        }
        if(prev_x == nx && prev_y == ny) {
            continue;
        }
        answer = max(answer, TetroMino[x][y] + makeStandardShape(nx, ny, x, y, depth+1, TetroMino, N, M));
    }
    return answer;
}

이 함수는 재귀적으로 호출되어 가능한 모든 깊이를 탐색하며, 각 깊이에서 테트로미노의 합을 계산합니다.

BFS (Breadth-First Search) - 너비 우선 탐색

BFS는 시작 노드에서 가까운 노드부터 차례로 탐색하고, 각 단계에서 모든 인접 노드를 방문한 후 다음 단계로 이동하는 방법입니다. 주로 큐를 사용하여 구현합니다.

BFS의 작동 원리:

1. 시작 노드 선택: 시작 노드를 큐에 추가합니다.
2. 큐에서 노드 꺼내기: 큐에서 노드를 꺼내어 현재 노드로 설정합니다.
3. 현재 노드 방문: 현재 노드를 방문하고, 방문한 노드를 표시합니다.
4. 인접 노드 추가: 현재 노드의 인접 노드를 큐에 추가합니다.
5. 반복: 큐가 비어 있을 때까지 2~4 단계를 반복합니다.

BFS의 장점:

• 최단 경로를 찾는 데 유리합니다.
• 모든 노드를 동일한 깊이에서 탐색할 수 있습니다.

BFS의 예시 (두 번째 코드의 shape4MaxSum 함수):

void shape4MaxSum(vector<vector<int>>& mat, int cnt, pair<int, int> cur, int sum) {
    int original = mat[cur.Y][cur.X];
    mat[cur.Y][cur.X] = -1;

    if (cnt >= 4) {
        max_sum = max(max_sum, sum);
        mat[cur.Y][cur.X] = original;
        return;
    }

    for (pair<int, int>& p : udlr) {
        int x = cur.X + p.X;
        int y = cur.Y + p.Y;

        if (x >= 0 && x < m && y >= 0 && y < n) {
            if (mat[y][x] != -1) {
                int value = mat[y][x];
                pair<int, int> new_p = make_pair(x, y);
                shape4MaxSum(mat, cnt + 1, new_p, sum + value);
            }
        }
    }
    mat[cur.Y][cur.X] = original;
}

이 함수는 특정 셀에서 시작하여 인접한 셀을 탐색합니다. 재귀적으로 호출되어 가능한 모든 방향으로 탐색을 진행합니다. 이 방식은 BFS보다는 DFS 방식에 가까운 탐색 방식이지만, 큐를 사용하지 않고 재귀 호출로 탐색을 구현하였습니다.

요약

• DFS: 깊이 우선 탐색, 재귀 또는 스택을 사용하여 깊게 탐색 후 백트래킹.
• BFS: 너비 우선 탐색, 큐를 사용하여 같은 깊이의 노드들을 먼저 탐색.

두 알고리즘 모두 문제의 성격에 따라 적절히 사용됩니다. 각기 다른 방식으로 노드를 탐색하여 최적의 솔루션을 찾을 수 있습니다.