[구름톤 챌린지 Week4(1)] 그래프 탐색 전략 (DFS, BFS)

이번 주차는 주로 그래프 탐색을 다뤄보았습니다.

'탐색'을 어떻게 할지에 따라 알고리즘의 성능에 크게 차이가 나게 되다보니, 이를 위해 전략을 잘 짜는 것이 중요합니다.

DFS (깊이 우선 탐색)과 BFS (너비 우선 탐색)

크게 두 가지를 정리하겠습니다.

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

DFS는 깊이를 우선적으로 탐색하는 알고리즘입니다.

한 노드에서 시작하여, 해당 노드에 연결된 노드들 중 하나를 선택해 계속 '깊게' 탐색하고, 더 이상 탐색할 곳이 없을 경우 이전 노드로 돌아와 다른 노드를 탐색합니다.

[자료구조] DFS는 스택이나 재귀 함수를 이용해 구현할 수 있습니다.

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

BFS는 너비를 우선적으로 탐색하는 알고리즘입니다.

한 노드에서 시작하여 해당 노드에 연결된 모든 노드(인접노드)를 먼저 탐색하고, 그 다음 레벨의 노드를 다시 너비 우선으로 탐색합니다.

[자료구조] BFS는 큐를 이용해 구현할 수 있습니다.

---

코드 구조

DFS 구조 (재귀)

def dfs(graph, start, visited):
    visited.add(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

DFS 구조 (큐)

def dfs_stack(graph, start):
    visited = set()  # 방문한 노드를 저장할 집합
    stack = [start]  # 시작 노드를 스택에 추가

    while stack:  # 스택이 비어있지 않은 동안
        vertex = stack.pop()  # 스택의 마지막 요소를 꺼냅니다.

        if vertex not in visited:  # 만약 해당 노드를 방문하지 않았다면
            print(vertex, end=" ")  # 해당 노드를 출력(또는 다른 작업)
            visited.add(vertex)  # 해당 노드를 방문한 것으로 표시

            # 아직 방문하지 않은 인접 노드들을 스택에 추가
            # 스택은 LIFO(Last In First Out)이므로 인접 노드를 역순으로 넣어줍니다.
            # 이렇게 하면 작은 순서의 노드부터 방문할 수 있습니다.
            stack.extend(reversed(graph[vertex]))

 

BFS 구조 (큐)

def bfs(graph, start, visited):
    queue = [start]  # 시작 노드를 큐에 추가합니다.
    visited.add(start)  # 시작 노드를 방문한 것으로 표시합니다.
    
    while queue:  # 큐가 비어있지 않는 동안
        vertex = queue.pop(0)  # 큐의 첫 번째 요소를 꺼냅니다.
        
        # 꺼낸 노드의 인접 노드들을 순회합니다.
        for neighbor in graph[vertex]:
            # 만약 인접 노드가 아직 방문되지 않았다면
            if neighbor not in visited:
                queue.append(neighbor)  # 큐에 인접 노드를 추가합니다.
                visited.add(neighbor)  # 그리고 방문한 것으로 표시합니다.

시간 복잡도

• DFS와 BFS 모두 일반적으로 O(V + E)의 시간 복잡도를 가집니다 (V: 노드의 수, E: 간선의 수).

사용 케이스

• DFS: 연결성만 체크하면 되거나, 모든 노드를 방문해야 하는 경우에 유용합니다. 또한, 스택을 사용하기 때문에 메모리 사용량이 상대적으로 적을 수 있습니다.
• BFS: 최단 경로를 찾는 문제에 더 적합합니다. 예를 들어, 가중치가 없는 그래프에서의 최단 경로 문제에 주로 사용됩니다.

메모리 사용량

• DFS: 스택을 사용하므로 깊이가 깊은 경우 메모리 사용량이 증가할 수 있습니다.
• BFS: 큐를 사용하므로 너비가 넓은 경우 메모리 사용량이 증가할 수 있습니다.

여기서 제 코드의 에러분석(Runtime Error)가 가능해졌습니다.

BFS가 모범답안인 알고리즘을 계속 DFS로 구현했던 것입니다. 

심지어 먼저 단방향 그래프를 생성한 후에 양방향 그래프를 생성하기도 하였습니다.

모범답안에는 그래프 생성, 방문 체크, 연합 카운트 등이 한 번의 루프에서 이루어집니다. 이 부분도 또한 챙겨가면 좋을 구조 같습니다.