반응형 큐2 BFS(너비 우선 탐색, Breadth-First Search) 알고리즘 - C언어, Java, Python 예시코드 포함, 시간복잡도 BFS(Breadth-First Search)는 그래프나 트리에서 널리 사용되는 탐색 알고리즘으로, 시작 정점에서 가까운 노드부터 탐색을 진행합니다. 경로를 찾거나 최단 거리를 계산하는 데 유용하며, 다양한 문제 해결에 활용됩니다. 1. BFS의 개념BFS는 큐(Queue) 자료구조를 기반으로 작동하며, 그래프의 각 레벨을 순차적으로 탐색합니다. 그래프의 각 정점을 방문하면서 모든 인접한 정점을 차례대로 탐색하므로, 깊이보다는 너비를 우선시합니다. 2. BFS의 동작 원리시작 정점을 큐에 삽입하고 방문 처리합니다.큐에서 정점을 하나씩 꺼내어 해당 정점의 모든 인접 정점을 탐색합니다.인접 정점 중 방문하지 않은 정점을 큐에 삽입하고 방문 처리합니다.큐가 빌 때까지 위 과정을 반복합니다.동작 구조도다음은 B.. 2024. 12. 19. 큐(Queue) 자료구조란? (C언어, Java, Python 예시코드) (1) 큐(Queue) 자료구조란?큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 선입선출(FIFO, First In First Out) 방식으로 동작하는 데이터 구조입니다. 이러한 특성 때문에 대기열, 작업 스케줄링, 메시지 처리 등 다양한 응용 분야에서 활용됩니다. (2) 큐의 기본 동작삽입(Enqueue): 큐의 끝(Rear)에 데이터를 추가.(예를들어 50을 큐에 추가할 경우 40에 위치한 rear를 한칸 오른쪽으로 밀고 그 칸에 추가)삭제(Dequeue): 큐의 앞(Front)에서 데이터를 제거.(현재 front가 위치한 10을 빼내고 deque 후 front는 20을 가리킴)보기(Peek): 큐의 앞에 있는 데이터를 제거하지 않고 확인.(단순히 현재 front가 가리키고 있는 값이 뭔지만 .. 2024. 12. 18. 이전 1 다음 반응형
