DFS (깊이 우선 탐색)

DFS는 그래프 탐색 알고리즘 중 하나로, 특정 시작 노드에서 출발하여 그래프의 모든 노드를 방문하는 방법 중 하나다.
DFS는 스택(Stack) 또는 재귀(Recursion)을 통해 구현된다.

DFS 동작 방식

1. 시작 노드를 방문하고, 해당 노드를 스택에 push(또는 재귀 호출)한다.

2. 현재 노드의 이웃 노드 중에서 방문하지 않은 노드를 하나 선택한다.

3. 선택한 이웃 노드로 이동하여 해당 노드를 방문하고, 스택에 push한다.

4. 위 과정을 반복하며, 현재 노드에 더 이상 방문할 이웃 노두가 없을 때까지 진행한다.

5. 현재 노드에서 더 이상 방문할 이웃 노드가 없다면, 스택에서 하나씩 노드를 pop하면서 이전 단계로 돌아간다.

6. 스택이 비어있을 때까지 반복한다.

1->2->3->4->5->6->7->8->9->10->11->12
위 순서대로 그래프를 탐색한다.

DFS는 그래프의 깊은 부분을 우선적으로 탐색하며, 스택을 사용하여 구현 할 때 가장 깊은 노드부터 역으로 탐색한다.

이 알고리즘을 사용하면 그래프에서 경로를 찾거나 연결된 컴포넌트를 찾는 등의 작업을 수행할 수 있다.

📃 code

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}

visited = []

def dfs_recursive(node, visited):
    # 방문처리
    visited.append(node)

    # 인접 노드 방문
    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(adj, visited)

    return visited

DFS를 재귀로 구현한 가장 기본적인 코드에 해당한다.

1. graph는 현재 딕셔너리 구조로 각 Node와 연결된 Node들을 담고 있다. (ex) 1 Node는 현재 2,3,4 노드를 가지고 있고, 2 Node는 5를...)

2. dfs_recursive는 재귀될 함수에 해당하며 파라미터로 Node와 visited(방문한 Node)를 넘겨준다.

3. 전달 받은 Node를 방문 list에 저장하고, 연결된 노드들을 순회하면서 해당 Node가 방문한 노드인지 확인하고, 방문하지 않은 Node라면 재귀 함수를 호출한다.

• 위 방식을 기본으로 그래프의 연결 요소 탐색 관련 문제를 해결할 수 있다.

---

BFS

BFS는 너비 우선 탐색으로 그래프나 트리 등의 자료 구조에서 루트 노드에서 시작하여 모든 형제 노드를 먼저 탐색하는 그래프 탐색 알고리즘 중 하나이다.

BFS 동작 방식

1. 너비 우선: BFS는 현재 노드에서 시작하여 인접한 모든 노드를 먼저 탐색한다. 다음 단계로 넘어가기 전에 현재 노드와 같은 레벨에 있는 모든 노드를 방문한다.

2. 큐(Queue) 사용: BFS는 큐 자료 구조를 사용하여 노드를 탐색한다. 시작 노드를 큐에 넣고, 큐에서 노드를 하나씩 꺼내면서 그 노드와 인접한 노드를 큐에 추가한다. 이렇게 큐에 들어가는 순서대로 탐색하므로 너비 우선 탐색이다.

3. 최단 경로: BFS는 그래프에서 최단 경로를 찾는 데 사용된다. 모든 노드를 현재 노드에서부터의 거리에 따라 탐색하므로, 첫 번째로 목표 노드에 도달하는 경로가 가장 짧은 경로다.

4. 탐색 과정: BFS는 모든 노드를 방문하고, 방문한 노드를 큐에 추가하고, 큐에서 노드를 하나씩 꺼내어 인접한 노드를 추가하는 과정을 반복한다. 큐가 빌 때까지 이 과정을 계속하며 모든 노드를 방문한다.

📃code

from collections import deque

graph = {
    1: [2, 3, 4],
    2: [5],
    3: [5],
    4: [],
    5: [6, 7],
    6: [],
    7: [3],
}


def bfs_queue(start):
    visited = [start]
    q = deque([start])

    while q:
        node = q.popleft()
        for adj in graph[node]:
            if adj not in visited:
                q.append(adj)
                visited.append(adj)

    return visited


assert bfs_queue(1) == [1, 2, 3, 4, 5, 6, 7]

1. 방문하지 않은 node의 경우 queue에 넣고 방문했다는 표시를 남긴다.

2. 인접한 노드들을 방문하면서, 방문한적이 없는 노드들을 queue에 넣는다.

3. queue에 node가 존재하지 않을때까지 반복한다.

4. queue의 경우 FIFO이기 때문에 먼저 들어온 노드를 확인하는 것이 깊이 우선이 아닌 넓이 우선 탐색임을 알 수 있다.

---

DFS / BFS 언제 쓰는거야???

DFS / BFS 두가지로 대부분의 문제 해결이 가능하다. 단 목표하는 Node의 위치가 그래프 상에 깊은 레벨에 존재한다면 DFS를 사용하고, 목표하는 Node의 위치가 그래프 상에 얕은 레벨에 존재한다면 BFS를 사용하는 것이 좋다.