[TIL 2024. 03. 14] DFS/BFS

오늘 한 일

• 오늘의 코드카타
• 오후 알고리즘 세션: tree, 이진탐색트리
• 알고리즘 문제 풀기: subtree, 이진탐색, 이진 힙 (swea)
• TIL 작성

 

DFS/BFS : 그래프 탐색 방법

 

1. dfs(깊이 우선 탐색, depth-first search)

• 사용하는 자료구조: stack / 원리: 재귀
• 주로 stack, 재귀함수 등으로 구현된다
• dfs 구현시에는 방문 여부를 변수에 저장해주는 게 중요하다. 방문 여부를 저장해놓지 않으면, 재귀시에 이미 방문한 노드를 다시 방문하며, 제대로 된 출력값이 나오지 않게 된다
• dfs에서 중요한 것은 '앞으로 방문할 노드'와 '이미 방문한 노드'를 기준으로 그래프를 탐색한다는 것이다 (사실 이 점은 bfs도 동일하게 중요하다!) 
  • nxt는 앞으로 방문할 노드 (cf. dfs(nxt): 재귀 호출)
  • visited = 이미 방문한 노드

 

다른 블로그에서 해당 그래프를 사용해서 dfs의 진행에 따라 stack이 쌓이는 과정을 상세히 적으신 걸 보고, 이해가 쉬운 것 같아서 나도 직접 과정을 스스로 정리해보기로 했다..

(출처: 블로그 '결국 빛나리라')

 

• 1에서 탐색을 시작한다 [1]
• 1과 연결된 노드 2,6,8 중 가장 작은 노드인 2를 방문한다 [1,2]
• 2와 연결된 노드는 1,3이고, (그 중 1은 이미 방문한 노드이므로) 3을 방문한다 [1,2,3]
• 3에서는 5,7 중 더 작은 수인 5를 방문한다 [1,2,3,5]
• 5에서는 방문하지 않은 노드인 7을 방문한다 [1,2,3,5,7]
• 7에서는 이제 방문하지 않은 곳이 없으므로, 7을 스택에서 꺼내고 5로 돌아간다 [1,2,3,5]
• 5에서 3으로 돌아간다 [1,2,3]
• 3에서 2로, 2에서 1로 돌아간다 [1,2] -> [1]
• 1에서 6,8 중 더 작은 수인 6을 방문한다 [1,6]
• 6에서 4를 방문한다 [1,6,4]
• 4에서는 더이상 방문가능한 인접노드가 없으므로 6으로 돌아간다 [1,6]
• 6에서 8을 방문한다 [1,6,8]
• 8을 포함해서 더이상 방문할 수 있는 인접노드들이 없으므로 모든 노드를 차례대로 스택에서 꺼내면서 돌아온다   [1,6] -> [1] -> [ ]

결론: 1->2->3->5->7->6->4->8

 

---

 

2. bfs(너비 우선 탐색, breadth-first-search)

• 사용하는 자료구조: 큐 / 원리: 큐의 자료구조
• 주로 큐를 사용하여 구현된다
• 앞서 언급했듯, bfs에서도  '앞으로 방문할 노드'와 '이미 방문한 노드'를 기준으로 그래프를 탐색한다는 점이 중요하다
• dfs와 bfs의 차이는 각각의 탐색이 사용하는 자료구조의 차이에서 기인한다. 즉, stack을 사용하는 dfs는 리스트의 가장 마지막 데이터를 우선적으로 탐색에 사용한다. 반면에, queue를 사용하는 bfs는 리스트의 가장 처음에 있는 데이터를 탐색에 우선 사용한다
• 사실 dfs나 bfs 모두 그래프 탐색 방법이므로, 왠만한 문제들은 두 가지 방법 모두로 코드 작성이 가능하지만, 알고리즘 문제에서 주어진 조건 등에 따라 유리한 알고리즘을 선택하는 것이 중요하다
  • q = 앞으로 가야 할 노드  (변수q에 저장(append)) (q = deque())
  • visited = 이미 방문한 노드

 

 

• 1에서 탐색을 시작한다 [1]
• 1이 queue에서 제거(pop)되고, 인접한 2,6,8이 작은 수부터 차례대로 큐에 추가된다 [2,6,8]
• 2가 제거되고, (2와 인접한 노드인) 3이 추가된다 [6,8,3]
• 6이 제거되고, (6과 인접한 노드들 중) 방문하지 않은 4가 큐에 추가된다 [8,3,4]
• 8이 제거되었지만, 더 이상 방문 가능한 인접노드가 없으므로 무시한다 [3,4]
• 3이 제거되고, 인접한 노드인 5,7이 큐에 추가된다 [4,5,7]
• 모든 노드를 방문했으므로 큐에서 모든 노드들을 차례대로 꺼내고 탐색이 종료된다 [5,7] -> [7] -> [ ]

결론: 1->2->6->8->3->4->5->7

 

---

DFS 구현

1. stack : 파이썬의 리스트 구조가 stack의 일종임

2. 재귀함수

3. (deque 사용)

 

 

BFS 구현

1. 큐 사용

2. (리스트 사용) : 리스트로 큐를 유사하게 구현

 

 

 

(참고)

Ch02. 그래프 탐색 알고리즘 : DFS & BFS (feat. 이것이 취업을 위한 코딩 테스트다)