깊이우선탐색2 그래프 탐색 - 깊이 우선 탐색 DFS DFS는 스택 or 재귀 이용해서 푼다1. 스택을 활용한 DFS탐색 전 시작 노드 정하기스택에 시작 노드를 Push스택에 있는 노드는 방문 안 한 노드 && 방문 예정 노드임스택이 비었는지 확인-> 비었으면 모두 방문한거니까 탐색 종료스택에서 노드 팝-> 팝한 원소는 최근 스택에 푸시한 노드팝한 노드의 방문 여부 확인-> 안했으면 방문방문한 노드와 인접 모든 노드 확인-> 안 했으면 노드를 스택에 푸시 1.1. 그림으로 보는 스택으로 만드는 DFS 1.2. 코드로 구현한 DFSsort함수 쓰려고 algorithm 추가했당. #include #include #include #include using namespace std;// 인접 리스트vector> AdjList;// 방문 여부vector bVisit.. 2025. 2. 4. 그래프 탐색 - DFS vs BFS 1. 경로 찾는 문제가 나온다면..?방법은 2개가 있다1) 더 이상 탐색할 노드 없을 때 까지 탐색해본다. 더 이상 탐색할 노드 없으면 최근 방문 노드로 되돌아가서 가지 않은 노드 방문한다2) 현재 위치에서 가장 가까운 노드 모두 싹 돌고, 다음 노드로 넘어감. 그 노드에서 또 다시 가장 가까운 노드부터 모두 방문이게 뭐냐? 각각 깊이 우선 탐색, 너비 우선 탐색임이해가 쉽도록 아래 그림을 확인해보자.1.1. 깊이 우선 탐색 1.2. 너비우선탐색2. 코테 풀 때!!!탐색은 해야하는데 최단 경로 구하는 거 아니면 DFS 쓰면 됨최단 경로 찾는다? BFS 갈겨~~~~ 2025. 2. 4. 이전 1 다음
