목록Engineering/Algorithm (1)

Jihun Oh

DFS, BFS

DFS (깊이 우선 탐색)스택, 재귀 또는 반복문으로 구현백트랙킹에 유용. 백트래킹은 탐색을 하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는 방식에서 유래. DFS는 백트래킹의 골격을 이루는 알고리즘. 한번 방문 후 가능성이 없는 경우에는 즉시 후보를 포기.제약 충족 문제 (스도쿠, 십자말 풀이, 8퀸 문제, 4색 문제, 배낭 문제, 문자열 파싱, 조합 최적화)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..
Engineering/Algorithm 2025. 4. 3. 23:26
이전 Prev 1 Next 다음