μλ§ μλ₯μ λμ»₯ λΆμ΄λ²λ¦¬κ³ , μ½ν μ€λΉ 4μΌμ μ¬ λμ ...
μμ£Ό λμ¨λ€λ μ νμ κΈνκ² κ³΅λΆν΄λ΄ λλ€ νν
DFSλ Depth First Search, κΉμ΄ μ°μ νμμ λλ€.
μ΄λ¦μ²λΌ μ΅λν κΉκ² νμν ν λ μ΄μ λλ¬ν μ μλ μν©μ΄λΌλ©΄ λ€μ μ΄μ μΌλ‘ λμκ°λλ€.
μ€μν κ²μ κΉκ² νμνκ³ λμ μ΄μ κ³Όμ μΌλ‘ λμκ°μΌ νλ€λ μ μ λλ€.
DFSλ μ¬κ·(μ€ν)λ₯Ό νμ©ν΄ ꡬννλ κ²½μ°κ° λ§μ΅λλ€. μ¦, λ°©λ¬Έν μ μλ μ§μ μ΄ μλ€λ©΄ κ·Έ μ§μ μ λ°©λ¬Ένλ ν¨μλ₯Ό μ¬κ·μ μΌλ‘ νΈμΆνκ³ , λ μ΄μ λ°©λ¬Έν κ³³μ΄ μλ€λ©΄ ν¨μλ₯Ό μ’ λ£νλ©΄ λ κ²μ λλ€.
λ€λ§, μ΄λ―Έ λ°©λ¬Ένλ μ§μ μ λ λ°©λ¬Ένλ©΄ ν¨μ¨μ΄ λ¨μ΄μ§κΈ° λλ¬Έμ μ΄μ μ λ°©λ¬Ένλ μ§μ μ λ€μ λ°©λ¬Ένμ§ μμμΌ ν©λλ€.
ν λ² λ°©λ¬Έν μ§μ μ μ΄λ€ μ²λ¦¬λ₯Ό ν΄μ λ μ΄μ λ°©λ¬Ένμ§ μλλ‘ λ§μμΌ νλ€λ κ²μ λλ€.
κ·Έλμ μ°λ¦¬λ visitedλΌλ λ°°μ΄μ νλ λ§λ€κ³ , κ·Έ λ²νΈμ μ§μ μ λ°©λ¬Έν μ μ΄ μλμ§ νμΈνλ©° μ§νν΄μΌ ν©λλ€.
BFSλ Breadth First Search, λλΉ μ°μ νμμ λλ€.
μ¬κ·(μ€ν)μ νμ©νλ DFSμ λ¬λ¦¬, BFSλ νλ₯Ό μ¬μ©ν©λλ€.
νλμ λ Έλμ λ°©λ¬Ένκ² λλ©΄, κ·Έ λ Έλμ μΈμ ν λ Έλ μ€ λ°©λ¬Έν μ μ΄ μλ λ€λ₯Έ λ Έλλ₯Ό λͺ¨λ νμ λ£μ΅λλ€.
μ°λ¦¬λ νκ° FIFO ꡬ쑰λΌλ κ²μ μκΈ° λλ¬Έμ, μ΄λ°μμΌλ‘ λ£κ² λλ©΄ μ΄νμ μ²μ λ£μλ λ Έλμ μ΄μ λ Έλλ₯Ό μμ°¨μ μΌλ‘ λ°©λ¬Ένκ² λ κ²μ λλ€.
μμ°μ€λ½κ² μ΄νμλ κ°κ°μ μ΄μλ€μ νμ λ£κ² λ ν λ°, μ΄λ°μμΌλ‘ μ§νλλ©΄
μμ λ Έλμ μ΄μ -> κ·Έ λ€μ λ Έλμ μ΄μ -> κ·Έ λ€μ λ€μ λ Έλμ μ΄μ
μμΌλ‘ λ°©λ¬Ένκ² λ κ²μ λλ€. μ¦, μμμ μ κΈ°μ€μΌλ‘ κ°μ₯ κ°κΉμ΄ μ μ λΆν° λ°©λ¬Ένκ² λλ κ²μ λλ€.
κ·Έλ λ€λ©΄ DFSμ BFSμ μ±λ₯ μ°¨μ΄λ?
κ²°λ‘ λ§ λ§νλ©΄ μ΄λ‘ μ μΌλ‘ λ³ μ°¨μ΄ μλ€κ³ ν©λλ€.
μ΄μ°¨νΌ λͺ¨λ λ Έλμ μ£μ§λ₯Ό λ°©λ¬Ένλ κ²μ΄κΈ° λλ¬Έμ μκ°λ³΅μ‘λ μ체λ λ‘ λμΌν©λλ€.
κ·Έλ¬λ μ€μ λ‘ μ½λλ₯Ό μ§κ²λλ©΄ DFSκ° μ½κ° λλ¦° νΈμΈλ°, κ·Έ μ΄μ λ μ¬κ·ν¨μμ μ€λ²ν€λ(ν¨μ μ€ν μ λ°μνλ μκ° μ§μ°) λλ¬Έμ λλ€.
νμ§λ§ ν° λ¬Έμ λ μκΈ° λλ¬Έμ, μν©μ λ°λΌ λ νΈν μκ³ λ¦¬μ¦μ μ νν΄μ μ¬μ©νλ©΄ λ©λλ€.
λ³΄ν΅ μ΅λ¨κ±°λ¦¬λ₯Ό ꡬνλ λ¬Έμ μλ BFSλ₯Ό μ¬μ©ν©λλ€.
BFSλ μ μμ μμμ μΌλ‘λΆν° κ°κΉμ΄ μ§μ λΆν° λ°©λ¬Ένκ² λκΈ° λλ¬Έμ
κ°μ€μΉκ° μ λΆ λμΌν κ·Έλνμμλ μ΅λ¨κ±°λ¦¬λ₯Ό νμ€νκ² κ΅¬ν΄μ€ μ μλ κ²μ λλ€.
μΆμ² μ½λνΈλ¦¬
'π μκ³ λ¦¬μ¦ > Code Tree' μΉ΄ν κ³ λ¦¬μ λ€λ₯Έ κΈ
[μ½λνΈλ¦¬] Greedy - 그리λ μκ³ λ¦¬μ¦ / λμ μ°μ΅λ¬Έμ (0) | 2023.02.22 |
---|---|
[μ½λνΈλ¦¬] Backtracking - λ°±νΈλνΉ / μ¬κ· μ°μ΅λ¬Έμ (0) | 2023.02.21 |
[μ½λνΈλ¦¬] TreeSet μ°μ΅λ¬Έμ (0) | 2023.02.09 |
[μ½λνΈλ¦¬] Tree Set (0) | 2023.02.09 |
[μ½λνΈλ¦¬] Hash Set μ°μ΅λ¬Έμ (0) | 2023.02.09 |