소소한 지식 저장소

1. BFS (너비 우선 탐색) - 큐(Queue) 활용BFS는 시작 노드에서 가까운 노드부터 차례대로 탐색합니다. 파이썬에서는 collections.deque를 사용하는 것이 속도면에서 가장 효율적입니다.Python from collections import dequedef bfs(graph, start, visited): # 1. 시작 노드를 큐에 넣고 방문 처리 queue = deque([start]) visited[start] = True # 큐가 빌 때까지 반복 while queue: # 2. 큐에서 하나의 원소를 뽑아 출력 (가장 먼저 들어온 것) v = queue.popleft() print(v, end=' ') ..

너비 우선 탐색 (BFS, Breadth-First Search)개요시작 정점 s에서 도달 가능한 모든 정점을 방문하는 탐색 기법.시작점으로부터의 거리가 가까운 순서대로 정점을 탐색하며, 가중치 없는 그래프에서 최단 경로를 찾는 데 사용됨.주요 자료구조큐 (Queue): 다음에 방문할 정점을 선입선출(FIFO) 방식으로 관리.color[u]: 정점의 방문 상태 표시 (white: 미발견, gray: 발견되었으나 미처리, black: 처리 완료).d[u]: 시작점 s로부터의 최단 거리 저장.pred[u]: 최단 경로 트리에서 부모 정점을 가리킴.알고리즘 코드BFS(G,s) { // 모든 정점 u에 대해 초기화 수행 for each u in V { color[u] = white ..