태그: BFS
5편
-
BFS vs DFS: 동작 방식·복잡도 비교와 문제 유형별 선택 기준
BFS는 큐로 층별로 퍼지고 DFS는 스택·재귀로 한 갈래를 끝까지 파고듭니다. 두 방식의 시간·공간 복잡도 차이와 최단 경로, 사이클 탐지, 연결 요소 문제에서 무엇을 골라야 하는지를 미로 탈출·섬의 개수 예제로 비교합니다.
-
BFS와 DFS: 큐·재귀로 구현하는 그래프 탐색과 최단 거리·연결 요소 문제
BFS는 큐로, DFS는 재귀와 스택으로 구현하면서 BFS로 가중치 없는 그래프의 최단 거리를 구하는 방법과 DFS로 연결 요소를 세는 방법을 미로 탈출·섬의 개수 문제로 익힙니다. Python 재귀 한도 문제도 다룹니다.
-
그래프 자료구조: 인접 리스트와 인접 행렬, 그래프 탐색 기초
인접 리스트와 인접 행렬의 메모리·탐색 비용 차이를 비교하고, BFS·DFS로 연결 요소 개수, 사이클 감지, 위상 정렬을 구현합니다. 친구 추천, 작업 의존성 해결, 미로 최단 경로 같은 실제 적용 예도 함께 다룹니다.
-
C++ queue와 stack: 컨테이너 어댑터 사용법과 BFS·DFS 활용
C++ STL의 stack·queue·priority_queue 사용법과 내부 동작 원리를 비교하고, DFS·BFS·작업 스케줄링 실전 예제와 커스텀 비교자 설정 등 흔한 컴파일 에러 해결법을 정리합니다.
-
C++ 그래프 알고리즘: BFS·DFS, 다익스트라, Kruskal·Prim 최소신장트리, Union-Find
지도 최단 경로, 친구의 친구 탐색, 빌드 의존성 순서, 최소 비용 배선 같은 문제에 맞춰 BFS·DFS, 위상 정렬, 다익스트라, Kruskal·Prim, Union-Find를 C++로 구현합니다. 음수 간선에서 다익스트라가 틀리는 이유도 설명합니다.