BFS
-
[SW 정글 19일차] DFS와 BFS기타/SW 사관학교 정글 2021. 8. 21. 01:42
이번 주차는 DFS, BFS, 위상정렬에 대해 공부하는 주차로 그냥 단순히 DFS가 무엇인지, BFS가 무엇인지 알고만 알고리즘 문제를 풀어와서 이번 기회에 이렇게 글로 정리하며 개념을 다잡으려고 한다. 1. DFS (Depth-First Search) DFS는 그래프 탐색 알고리즘 중 하나로 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘으로 시작점부터 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하고 넘어가는 방법이다. DFS는 스택 자료구조나 재귀함수를 이용하여 구현할 수 있고 노드를 탐색 전에 방문 여부를 검사해야한다. DFS의 시간 복잡도는 인접 리스트로 표현된 그래프에서는 O(N+E)이고 인접 행렬로 표현된 그래프에서는 O(N^2)이다. 그래프 탐색이란? 그래프에서 하..