backtracking
-
DFS, BFSProgramming/leetcode 2021. 2. 23. 22:44
그래프 순회 이론 정리 DFS - 깊이 우선 탐색, Stack과 재귀 호출로 구현되며 Back-Tracking과 같이 사용하면 뛰어난 효과 BFS - 너비 우선 탐색, 주로 Queue로 구현하며 최단 경로 문제에서 많이 사용됨(다익스트라 알고리즘) 코딩테스트에서 대부분의 그래프 탐색은 DFS로 이루어짐 DFS - Stack과 재귀 호출로 구현 ex) graph = { 1:[2,3,4], 2:[5], 3:[5], 4:[], 5:[6,7], 6:[], 7:3} 재귀 호출로 구현 graph = { 1:[2,3,4], 2:[5], 3:[5], 4:[], 5:[6,7], 6:[], 7:[3]} def recursive_dfs(v, discovered=[]): discovered.append(v) for w in ..