너비우선탐색2 그래프 탐색 - 너비 우선 탐색(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. 그래프 탐색 - DFS vs BFS 1. 경로 찾는 문제가 나온다면..?방법은 2개가 있다1) 더 이상 탐색할 노드 없을 때 까지 탐색해본다. 더 이상 탐색할 노드 없으면 최근 방문 노드로 되돌아가서 가지 않은 노드 방문한다2) 현재 위치에서 가장 가까운 노드 모두 싹 돌고, 다음 노드로 넘어감. 그 노드에서 또 다시 가장 가까운 노드부터 모두 방문이게 뭐냐? 각각 깊이 우선 탐색, 너비 우선 탐색임이해가 쉽도록 아래 그림을 확인해보자.1.1. 깊이 우선 탐색 1.2. 너비우선탐색2. 코테 풀 때!!!탐색은 해야하는데 최단 경로 구하는 거 아니면 DFS 쓰면 됨최단 경로 찾는다? BFS 갈겨~~~~ 2025. 2. 4. 이전 1 다음
