그래프 탐색
- 어떤 것들이 연속해서 이어질 때 모두 확인하는 방법
- Graph : Vertex(어떤것. 노드) + Edge(이어지는 것. 연결선)
BFS
- 너비 우선 탐색 : 자기 자식 우선 탐색
- 시작점에 연결된 vertex찾기 -> 찾은 vertex를 queue에 저장
DFS
- 깊이 우선 탐색 : 자식의 자식을 우선 탐색 깊이 우선 탐색 : 자식의 자식을 우선 탐색
- 연결된 vertex 찾기 -> 찾은 vertex를 stack에 저장
시간복잡도
- 알고리즘이 얼마나 오래 걸리는지
- Big-O
- BFS : O(V+E)
사용 자료구조
- BFS
- 검색할 그래프
- 방문 여부 확인(재방문 금지 목적)
- Queue : BFS 실행