[02]자료구조(그래프),알고리즘 (그래프의 탐색 - BFS, DFS, 다익스트라, 플로이드-워셜)

• 그래프는 여러 개의 점(노드)들이 선(간선)으로 연결된 구조를 나타내며, 인접행렬과 인접 리스트로 표현할 수 있다.

• 그래프 탐색 방법에는 BFS(너비 우선 탐색)와 DFS(깊이 우선 탐색)가 있으며, 각각 큐와 스택을 사용하여 탐색을 진행한다.

• 백트래킹과 다익스트라 알고리즘을 설명하며, 백트래킹은 스택을 이용한 재귀 호출로 구현하고, 다익스트라는 BFS의 응용으로 최단 경로를 찾는 알고리즘으로 우선순위 큐를 사용하여 시간 단축이 가능함을 강조함.

• 플로이드-워셜 알고리즘은 모든 정점에서 각 정점까지의 최단 거리를 구하는 방법으로, O(V^3)의 시간 복잡도를 가지며, 그래프 탐색 유형에는 미로 탐색과 정점 탐색이 있음을 설명함.