Leta Learns

BFS (너비 우선 탐색) : 현재 정점과 인접한 정점들에 대해 우선적으로 탐색하는 방식 => 넓게(wide) 탐색. 큐(Queue)를 이용해서 구현. 방문한 정점에 대해 표시하지 않는 경우, 무한루프에 빠질 가능성 有 => 각 정점의 기 방문 여부 저장 (visited) 아래로 깊은 그래프에 대해 좋은 성능을 기대할 수 있다. ( -> 아래로 깊은 그래프에서 해가 중간에 있는 경우) BFS의 과정 BFS 시간 복잡도 (DFS와 동일) 시간 복잡도 (N: 노드 수, E: 에지 수) 인접 행렬로 표현된 그래프 => O(N^2) 인접 리스트로 표현된 그래프 => O(N+E) 희소 그래프 (Sparse Graph)의 경우, 인접리스트 사용이 유리 -> 그래프 내에 적은 숫자의 간선만을 가지는 그래프 DFS v..