목록2025/08/14 (1)
개발자공부일기
DFS/BFS
DFS (Depth-First Search)1. DFS란?DFS는 깊이 우선 탐색이라 하며, 한 정점에서 시작해 갈 수 있는 한 깊이 들어갔다가, 더 이상 갈 수 없으면 이전 지점으로 되돌아오는(backtracking) 방식의 그래프 탐색 알고리즘이다.스택(Stack) 자료구조를 사용하거나, 재귀 호출을 통해 시스템 호출 스택을 활용한다.2. DFS의 원리시작 정점을 방문하고 방문 표시를 한다.현재 정점에서 갈 수 있는 이웃 정점 중 아직 방문하지 않은 정점을 하나 선택해 이동한다.이동한 정점에서 1~2 과정을 반복한다.더 이상 방문할 이웃이 없으면 이전 정점으로 되돌아가 다른 경로를 탐색한다.모든 정점을 방문할 때까지 반복한다.3. 반복형 DFS 코드vector dfs_iter(int start, co..
코딩테스트/알고리즘
2025. 8. 14. 23:30