πŸ’» Computer Science/- Data Structure, Algorithm

[μ•Œκ³ λ¦¬μ¦˜-이둠]κ·Έλž˜ν”„μ˜ 검색 μ•Œκ³ λ¦¬μ¦˜ - DFS(Stack)와 BFS(Queue)

Wonit 2020. 3. 1. 13:41
κ·Έλž˜ν”„ μžλ£Œκ΅¬μ‘°μ—μ„œ λ…Έλ“œμ˜ Dataλ₯Ό κ²€μƒ‰ν•˜λŠ” λ°©λ²•μ—λŠ” μ—¬λŸ¬ 방법이 μžˆκ² μ§€λ§Œ λŒ€ν‘œμ μΈ DFS, BFSλ₯Ό ν•™μŠ΅ν•΄λ³΄μž.

κ·Έλž˜ν”„

 

κ·Έλž˜ν”„λž€?

 

μœ„μ™€ 같은 λͺ¨μŠ΅μœΌλ‘œ λ…Έλ“œλ“€ κ°„μ˜ 관계λ₯Ό κ°„μ„ μœΌλ‘œ μ—°κ²° ν˜Ήμ€ λΉ„μ—°κ²° λ˜μ–΄μžˆλŠ” 자료ꡬ쑰 이닀.

 

μ§€κΈˆμ€ μžλ£Œκ΅¬μ‘°μ— λŒ€ν•œ μ„€λͺ…을 ν•˜λŠ” μ‹œκ°„μ΄ μ•„λ‹ˆλ―€λ‘œ λ„˜μ–΄κ°€μ„œ λ°”λ‘œ κ·Έλž˜ν”„μ˜ 검색 μ•Œκ³ λ¦¬μ¦˜μ„ μ•Œμ•„λ³΄μž.

 

Depth-First-Search(DFS)

 

 

깊이 μš°μ„  검색인 DFSλŠ”

  • Inorder
  • Preorder*
  • Postorder
    κ³Ό 같은 것듀이 ν¬ν•¨λ˜λ©° μ‹œμž‘ λ…Έλ“œμ—μ„œλΆ€ν„° ν•΄λ‹Ή λ…Έλ“œμ˜ μžμ‹ λ…Έλ“œλ‘œ λκΉŒμ§€ λ‚΄λ €κ°€λ©° κ²€μƒ‰ν•˜λŠ” 방식을 λœ»ν•œλ‹€.

 

Breath-First-Search(BFS)

 

넓이 μš°μ„  검색인 BFSλŠ”

 

 

μ‹œμž‘ λ…Έλ“œμ—μ„œ μžμ‹ μ˜ ν˜•μ œλ…Έλ“œ (Level) λ‹¨μœ„λ‘œ κ²€μƒ‰ν•˜λŠ” 방법을 λœ»ν•œλ‹€.

 

DFS와 BFS의 차이

 

 

DFS의 κ΅¬ν˜„

 

λ‹€μŒκ³Ό 같은 κ·Έλž˜ν”„κ°€ μžˆλ‹€κ³  κ°€μ •ν•˜μ˜€μ„ λ•Œ DFS와 BFSλ₯Ό μ΄μš©ν•˜μ—¬ κ·Έλž˜ν”„λ₯Ό μˆœνšŒν•΄λ³΄μž.

 

Stack

 

깊이 μš°μ„  검색 인 DFSλŠ” 주둜 Stack으둜 κ΅¬ν˜„μ„ ν•œλ‹€.

 

μŠ€νƒμ— μ‹œμž‘ λ…Έλ“œλΆ€ν„° λ„£κ³  λ…Έλ“œλ₯Ό Pop ν•  λ•Œ ν•΄λ‹Ή λ…Έλ“œμ˜ μžμ‹μ„ μŠ€νƒμ— λ„£μ–΄μ€€λ‹€.

 

1. 0을 μŠ€νƒμ—μ„œ pop 그의 μžμ‹μΈ 1을 push ν•œλ‹€.

 

2. 1을 μŠ€νƒμ—μ„œ popν•˜κ³  그의 μžμ‹μΈ 2와 3을 push ν•œλ‹€.

 

3. 3을 μŠ€νƒμ—μ„œ Popν•˜κ³  그의 μžμ‹μΈ 4와 5λ₯Ό push ν•œλ‹€.

 

4. 5λ₯Ό μŠ€νƒμ—μ„œ pop ν•˜κ³  그의 μžμ‹μΈ 7κ³Ό 6을 push ν•œλ‹€.

 

5. 6을 μŠ€νƒμ—μ„œ popν•˜κ³  그의 μžμ‹μΈ 8을 push ν•œλ‹€.

 

6. λ‚˜λ¨Έμ§€ λ…Έλ“œλ₯Ό popν•œλ‹€.

 

BFS의 κ΅¬ν˜„

 

Queue

 

넓이 μš°μ„  검색인 BFSλŠ” 주둜 Queue둜 κ΅¬ν˜„μ„ ν•œλ‹€.

 

0을 μ‹œμž‘λ…Έλ“œλ‘œ ν•˜μ—¬ 그의 μžμ‹μΈ 1을 enqueue ν•œλ‹€.

 

 

νμ—μ„œ 1을 dequeue ν•˜κ³  그의 μžμ‹μΈ 2와 3을 enqueue ν•œλ‹€.

 

νμ—μ„œ 2λ₯Ό dequeueν•˜κ³  그의 μžμ‹μΈ 4λ₯Ό enqueueν•œλ‹€.

 

νμ—μ„œ 3을 dequeue ν•˜κ³  그의 μžμ‹μΈ 5λ₯Ό enqueue ν•œλ‹€.

 

νμ—μ„œ 4λ₯Ό dequeue ν•˜κ³  그의 μžμ‹μ„ enqueue ν•΄μ•Όν•˜μ§€λ§Œ 이미 좜λ ₯λ˜μ–΄ μžˆμœΌλ―€λ‘œ λ„˜μ–΄κ°„λ‹€.

 

νμ—μ„œ 5λ₯Ό dequeue ν•˜κ³  그의 μžμ‹μ„ enqueue ν•΄μ€€λ‹€.

λͺ¨λ“  λ…Έλ“œλ₯Ό λ°©λ¬Έν•˜μ—¬ 더 이상 큐에 남은 λ…Έλ“œκ°€ 없을 λ•Œ κΉŒμ§€ μœ„μ™€ 같은 과정을 λ°˜λ³΅ν•˜μ—¬ κ²°κ³Όλ₯Ό 좜λ ₯ν•œλ‹€.