뒤돌아서면 까먹고, 뒤돌아서면 까먹는 BFS 기본 코드

코테 인강 선생님이 30초만에 짜야된다고 외우라고 3천번 정도 말씀하셨다.

BFS

BFS는 그래프나 트리에서 가장 가까운 노드부터 차례로 탐색하는 알고리즘이다.즉, 한 단계(level)의 모든 노드를 탐색한 후 다음 단계로 넘어가는 방식으로 진행된다.

1. 탐색을 시작할 시작 노드(start node)를 큐(queue)에 삽입한다.
2. 큐에서 노드를 하나 꺼내어 방문한다.
3. 해당 노드와 연결된 아직 방문하지 않은 노드들을 큐에 추가한다.
4. 위 과정을 큐가 빌 때까지 반복한다.

트리의 레벨 순회(BFS)

• 트리의 레벨 순회(BFS) 구현으로, 노드의 왼쪽과 오른쪽 자식을 차례로 탐색하는 구조

from collections import deque

def levelOrder(root):
    visited = []
    if root is None:
        return 0
    q = deque()
    q.append(root)
    while q:
        cur_node = q.popleft()
        visited.append(cur_node.value)

        if cur_node.left:
            q.append(cur_node.left)
        if cur_node.right:
            q.append(cur_node.right)
    return visited

그래프 탐색 BFS

그래프 탐색 BFS로, 인접 리스트 방식으로 연결된 모든 정점을 탐색

from collections import deque

def bfs(graph, start):
    q = deque([start])  # 큐 생성 및 시작 노드 삽입
    visited = set([start])  # 방문한 노드 저장

    while q:
        cur_node = q.popleft()  # 큐에서 노드 꺼내기
        print(cur_node, end=" ")  # 방문한 노드 출력

        for next_node in graph[cur_node]:  # 연결된 노드 탐색
            if next_node not in visited:  # 아직 방문하지 않았다면
                q.append(next_node)  # 큐에 추가
                visited.add(next_node)  # 방문 표시

특징

• deque를 활용하여 큐(queue) 자료구조를 사용
• while 루프를 통해 큐에서 요소를 하나씩 꺼내며 탐색을 진행

탐색 대상

• 첫 번째 코드는 이진 트리(Binary Tree) 를 탐색하는 BFS
• 두 번째 코드는 그래프(Graph) 를 탐색하는 BFS

데이터 구조

• 첫 번째 코드는 트리 노드(TreeNode) 를 사용하여 왼쪽(left)과 오른쪽(right) 자식을 탐색
• 두 번째 코드는 인접 리스트(graph) 를 사용하여 현재 노드와 연결된 모든 이웃을 탐색

방문 처리 방식

• 첫 번째 코드는 visited 리스트를 이용하여 탐색한 노드의 값을 저장
• 두 번째 코드는 visited 딕셔너리를 이용하여 방문한 노드 자체를 체크

초기 조건

• 첫 번째 코드는 root가 None일 경우 0을 반환하여 탐색을 종료
• 두 번째 코드는 start_v를 visited에 추가하면서 탐색을 시작