큐3 그래프 탐색 - 너비 우선 탐색(BFS) DFS는 스택을 사용해서 구현했었다BFS는 큐를 사용한다!! 큐는 들어간 순서대로 나오는 거 FIFO 1) 큐가 비었나 확인(비었으면 모든 노드 다 방문한 거임. 탐색종료)2) 큐에서 노드를 팝3) 방금 막 팝한 노드 인접 노드 확인-> 그 중 방문 안한거 있으면 그 노드 큐에 푸쉬 후 방문 처리 1. 그림으로 보는 큐를 이용한 DFS 2. 코드로 보는 큐로 구현한 DFS#include #include #include #include using namespace std;// 인접 리스트vector> AdjList;// 방문 여부vector bVisited;// BFS 함수void BFS(int StartNode){ queue Q; Q.push(StartNode); bVisite.. 2025. 2. 5. STL- 큐 1. 큐 (Queue)?큐는 줄을 서다. 큐 (Queue)?먼저 들어간 게 먼저 나오는 First In First Out 구조(선입선출)코테에서 STL에서 제공하는 큐 사용해도 충분함~~~~~STL 제공하는 큐의 push(), pop(), front(), empty()는 모두 O(1)2. 큐에서 필요한 함수와 변수bool IsFull() : 큐의 데이터 갯수가 MaxSize인지 아닌지 true/ false 반환bool IsEmpty() : 큐에 데이터 0개인지 아닌지 true/ false 반환void Push(DataType Data): 큐데 데이터 삽입DataType Pop() : 큐에 데이터 제거하고 그 데이터 반환int front : 가장 마지막에 팝한 위치 (한 개도 팝 안 했다면 맨 처음 들어간.. 2025. 1. 28. [자료구조] DFS와 BFS DFS 와 BFS란?DFS (Depth-First Search)와 BFS (Breadth-First Search)는 그래프 탐색 알고리즘그래프의 모든 노드를 탐색하는 방법임두 알고리즘은 탐색의 순서와 방식에서 차이 있음시간복잡도는 DFS/ BFS 동일함-> 왜냐? 모든 조건 내 모든 노드를 검색하니까--> But, 최단거리 구할 때는 BFS가 유리함 1. DFS (Depth-First Search)- 개념: DFS는 깊이 우선 탐색한 노드에서 시작하여 다음 분기로 넘어가기 전에!!해당 분기를 따라 최대한 깊이 내려가며 탐색하는 방법 - 특징: 스택 (Stack) 사용재귀 호출을 사용할 수 있음한 경로를 끝까지 탐색한 후, 다른 경로를 탐색 2. BFS (Breadth-First Search)- 개념:BF.. 2024. 8. 2. 이전 1 다음
