스택4 그래프 탐색 - 깊이 우선 탐색 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. SLT-스택 1. 스택이란?쌓는다후입선출: 마지막 들어간 게 먼저 나오는 것LIFO : Last In First OutPush: 삽입하기Pop: 꺼내기2. 스택에 필요한 연산과 변수Push : 스택에 데이터 푸쉬하는 함수Pop : 최근 데이터 팝하고 그 데이터 반환IsFull : 스택에 들어 있는 데이터가 MaxSize인지 확인 -> 맞다면 True/ 아니면 False IsEmpty : 스택에 데이터가 한개도 없다면 True/ 있다면 FalseTop : 최근에 푸시한 데이터 위치Data[MaxSize]: 스택 데이터 관리하는 배열 3. 예시 코드top() -> 최근 넣은 데이터 반환pop() -> 최근 넣은 데이터 삭제. 아무것도 반환X 2025. 1. 27. [자료구조] 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. [자료구조] Stack 구현 (C++) 금요일에 짰던 초밥 스택을 Push랑 Pop하는 걸 복습할 겸 아래와 같이 다시 새로 짜보았다.감자초밥에서 초밥 한 접시 주문해보세요 :) #include using namespace std;struct SushiSt { string name = "초밥이름"; int price = 1004;};// 내가 구매한 접시 푸쉬하고 팝하려고 만든 클래스임class Stack { enum { MAX_ARRAY_SIZE = 10 };public: Stack() : m_top(0) { } // m_top을 0으로 초기화 해줌 void Push(string name, int price) { m_sushiAry[m_top].name = name; m_sushiAry[m_top++].price = price; } v.. 2023. 3. 19. 이전 1 다음
