th42500의 TIL

BFS (Breadth-First Search) ✔ 그래프 탐색 알고리즘 탐색(Search)이란 많은 양의 데이터 내에서 원하는 데이터를 찾는 과정을 의미 ✔ BFS 그래프에서 부모 노드를 먼저 방문한 후, 방문했던 부모 노드의 자식 노드를 차례로 탐색하는 알고리즘으로, 너비 우선 탐색이라고도 불림 선입선출 형태의 Queue자료구조 활용 트리일 경우 순회 방향 (번호 순서대로 진행) 시간복잡도 : O(V+E) 👉 V : 노드 수, E : 에지 수 ✔ 동작 과정 1️⃣ 탐색 시작 노드를 Queue에 삽입하고 방문 처리 2️⃣ Queue에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 3️⃣ 2️⃣ 과정을 수행할 수 없을 때까지 반복 ✔ 예시 1️⃣ 시작 ..

DFS (Depth-First Search) ✔ 그래프 탐색 알고리즘 탐색(Search)이란 많은 양의 데이터 내에서 원하는 데이터를 찾는 과정을 의미 ✔ DFS 특징 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘으로, 깊이 우선 탐색이라고도 불림 재귀적으로 구현 또는 후입선출 구조의 스택을 적용 트리일 경우 순회 방향 (번호 순서대로 진행) 시간복잡도는 O(V+E) 👉 V : 노드 수, E : 에지 수 ✔ 동작 과정 1️⃣ 탐색 시작 노드를 스택에 삽입하고 방문 처리 2️⃣ 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드 꺼내기 3️⃣ 더 이상 2️⃣번의 과정을 수행할 수 없을 때까지 반복 ..