[μκ³ λ¦¬μ¦-μ΄λ‘ ]κ·Έλνμ κ²μ μκ³ λ¦¬μ¦ - DFS(Stack)μ BFS(Queue)
κ·Έλν μλ£κ΅¬μ‘°μμ λ Έλμ 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 ν΄μ€λ€.
λͺ¨λ λ Έλλ₯Ό λ°©λ¬Ένμ¬ λ μ΄μ νμ λ¨μ λ Έλκ° μμ λ κΉμ§ μμ κ°μ κ³Όμ μ λ°λ³΅νμ¬ κ²°κ³Όλ₯Ό μΆλ ₯νλ€.