알고리즘 - BFS, DFS

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

• 현재 노드에서 가장 인접한 노드를 우선적으로 탐색는 알고리즘
• 최단 경로를 보장해줌
• Queue를 사용

from collections import deque

def bfs(graph, start):
    visited = set()  # 방문한 노드 기록
    queue = deque([start])  # BFS를 위한 큐 초기화
    visited.add(start)
    
    while queue:
        node = queue.popleft()  # 큐에서 노드 하나를 꺼냄
        print(node, end=" ")   # 노드 처리 (여기선 출력)
        
        # 현재 노드의 인접 노드 중 방문하지 않은 노드를 큐에 추가
        for neighbor in graph[node]:
            if neighbor not in visited:
                queue.append(neighbor)
                visited.add(neighbor)

# 그래프 예제 (인접 리스트)
graph = {
    1: [2, 3],
    2: [4, 5],
    3: [6],
    4: [],
    5: [6],
    6: []
}

# BFS 실행
bfs(graph, start=1)

동작 원리

• 시작 노드를 큐에 추가하고 방문 처리.
• 큐에서 노드를 꺼내, 해당 노드와 연결된 인접 노드 중 방문하지 않은 노드를 큐에 추가.
• 큐가 빌 때까지 위 과정을 반복.

출력 결과
위 그래프에서 start=1로 BFS를 실행하면 다음과 같은 순서로 탐색:
1 2 3 4 5 6

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

• 현재 노드에서 갈 수 있는 가장 깊은 노드를 우선적으로 탐색하는 알고리즘.
• Stack 사용 (다만, 컴퓨터는 구조적으로 stack의 원리를 사용하기 때문에, stack 함수를 따로 쓸 필요는 없음)

def dfs_stack(graph, start):
    visited = set()  # 방문한 노드 기록
    stack = [start]  # 스택 초기화
    
    while stack:
        node = stack.pop()  # 스택에서 노드 꺼냄
        if node not in visited:
            visited.add(node)  # 노드 방문 처리
            print(node, end=" ")  # 노드 처리 (여기선 출력)
            
            # 인접 노드를 스택에 추가 (역순으로 넣으면 올바른 순서 탐색 가능)
            for neighbor in reversed(graph[node]):
                if neighbor not in visited:
                    stack.append(neighbor)

# 실행
dfs_stack(graph, start=1)

출력결과
1 3 6 2 5 4

작동 원리 이해 후 다양한 코딩 문제에 적용시키기