[그래프] 그래프 순회 - DFS(깊이 우선 탐색), BFS(너비 우선 탐색), 백트래킹

ㅁ 그래프 순회 : 그래프의 각 정점을 방문하는 것

    1) 깊이 우선 탐색(DFS) : 多. 스택이나 재귀로 구현. 백트래킹

    2) 너비 우선 탐색(BFS) : 큐 구현. 그래프의 최단 경로 문제. 재귀로 동작하지 않음(큐 반복만 가능)

 

---

ㅁ 백트래킹(Backtracking)

- 탐색하다가 가능성이 없다고 판단되는 즉시 후보를 포기(backtrack)해 정답을 찾아가는 알고리즘

- 깊이 우선 탐색(DFS)보다 광의적

- 주로 재귀로 구현

- 가고 되돌아오고를 반복함 : 브루트 포스와 유사하지만 한번 방문 후 포기할 수 있다(=트리의 가지치기)는 점에서 매번 같은 경로를 방문하는 브루트 포스와 차이가 있음

- 제약 충족 문제(CSP)에 특히 유용함

 

ㅁ 제약 충족 문제(Constraint Satisfaction Problems) : 수많은 제약 조건을 충족하는 상태를 찾아내는 수학 문제

- AI, 경영 과학 분야에서 연구多

- 휴리스틱 및 조합 탐색 같은 개념을 결합하여 시간 내에 문제를 해결함

(ex) 스토쿠(1~9의 숫자를 한 번만 넣는 제약 조건을 충족하는 정답을 찾아내는 문제 유형)

(ex) 퍼즐문제(십자말 풀이, 8퀸 문제, 4색 문제), 배낭 문제, 문자열 파싱, 조합 최적화 문제 등

 

 

---

참고자료

- 박상길, <파이썬 알고리즘 인터뷰>