BFS와 DFS: 그래프 탐색

from collections import deque

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E'],
}


def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order


print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']


# BFS는 시작점에서 거리별로 탐색
# A (거리 0) → B, C (거리 1) → D, E, F (거리 2)

# DFS 재귀
def dfs_recursive(graph, node, visited=None, order=None):
    if visited is None:
        visited = set()
        order = []
    visited.add(node)
    order.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, order)
    return order


print(dfs_recursive(graph, 'A'))  # ['A', 'B', 'D', 'E', 'F', 'C']


# DFS 스택 (재귀 없이)
def dfs_iterative(graph, start):
    visited = {start}
    stack = [start]
    order = []

    while stack:
        node = stack.pop()
        order.append(node)
        for neighbor in graph[node]:  # 역순 추가하면 재귀와 같은 결과
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)

    return order


print(dfs_iterative(graph, 'A'))

# 무가중치 그래프에서 최단 경로 — BFS
def shortest_path(graph, start, end):
    if start == end:
        return [start]

    visited = {start}
    queue = deque([(start, [start])])

    while queue:
        node, path = queue.popleft()
        for neighbor in graph[node]:
            if neighbor == end:
                return path + [neighbor]
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None  # 경로 없음


print(shortest_path(graph, 'A', 'F'))  # ['A', 'C', 'F']
print(shortest_path(graph, 'D', 'F'))  # ['D', 'B', 'E', 'F']


# 가중치 있으면 → Dijkstra (모듈 5에서)

import requests
from bs4 import BeautifulSoup
from urllib.parse import urljoin

# ⚠️ robots.txt 준수 + 본인 사이트만
def crawl_bfs(start_url, max_pages=10):
    visited = {start_url}
    queue = deque([start_url])
    pages = []

    while queue and len(pages) < max_pages:
        url = queue.popleft()
        try:
            r = requests.get(url, timeout=5)
            pages.append((url, len(r.text)))

            soup = BeautifulSoup(r.text, 'html.parser')
            for link in soup.find_all('a', href=True):
                full_url = urljoin(url, link['href'])
                if full_url not in visited and full_url.startswith(start_url):
                    visited.add(full_url)
                    queue.append(full_url)
        except Exception:
            continue

    return pages


# pages = crawl_bfs('https://my-site.local', max_pages=20)

import os

def find_files_dfs(root, pattern):
    """DFS로 파일 찾기 — 재귀"""
    matches = []
    for entry in os.listdir(root):
        path = os.path.join(root, entry)
        if os.path.isdir(path):
            matches.extend(find_files_dfs(path, pattern))
        elif pattern in entry:
            matches.append(path)
    return matches


# matches = find_files_dfs('src', '.tsx')
# print(f"찾은 파일: {len(matches)}개")

# 컴포넌트 트리 (CH.21에서 정의)
component_tree = {
    'App': ['Header', 'Main', 'Footer'],
    'Header': ['Logo', 'Nav'],
    'Nav': ['NavItem1', 'NavItem2'],
    'Main': ['Article'],
    'Article': ['Title', 'Content'],
    'Logo': [], 'NavItem1': [], 'NavItem2': [],
    'Title': [], 'Content': [], 'Footer': [],
}

# 모든 컴포넌트 + 깊이
def render_tree(graph, node, depth=0):
    print('  ' * depth + node)
    for child in graph.get(node, []):
        render_tree(graph, child, depth + 1)


render_tree(component_tree, 'App')
# DFS — 한 가지 끝까지 갔다가 돌아옴

BFS 사용:
- 최단 경로 (무가중치)
- 레벨별 처리 (트리의 같은 깊이)
- 가까운 것부터 (지인의 지인)

DFS 사용:
- 백트래킹 (8 Queens, 스도쿠)
- 사이클 탐지
- 위상 정렬
- 메모리 제약 (스택 깊이만)