DFS
Stack 혹은 재귀함수(Recursion)으로 구현.
- 경로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게되면 다른 방향으로 다시 탐색을 진행
- 모든 노드를 방문하는 경우에 이 방법을 사용.
시간 복잡도
- 이접 리스트 : O(V+E)
- 인접 행렬 : O(V^2)
BFS
Queue 를 사용해서 구현
시간 복잡도
- 이접 리스트 : O(V+E)
- 인접 행렬 : O(V^2)
BFS는 다음의 경우 효과적으로 풀이할 수 있다.
1. 최소 비용 문제
2. 간선의 가중치가 1인 경우
3. 정점과 간선의 개수가 적다. (시간 제약, 메모리 제한 내에 만족.)
hyunho