λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

πŸ“ μ•Œκ³ λ¦¬μ¦˜/Code Tree

[μ½”λ“œνŠΈλ¦¬] DFS / BFS

728x90

μ†Œλ§ˆ μ„œλ₯˜μ— 덜μ»₯ 뢙어버리고, μ½”ν…Œ μ€€λΉ„ 4일전사 도전...

자주 λ‚˜μ˜¨λ‹€λŠ” μœ ν˜•μ„ κΈ‰ν•˜κ²Œ κ³΅λΆ€ν•΄λ΄…λ‹ˆλ‹€ ν•˜ν•˜

 


DFSλŠ” Depth First Search, 깊이 μš°μ„  νƒμƒ‰μž…λ‹ˆλ‹€.

μ΄λ¦„μ²˜λŸΌ μ΅œλŒ€ν•œ 깊게 νƒμƒ‰ν•œ ν›„ 더 이상 도달할 수 μ—†λŠ” 상황이라면 λ‹€μ‹œ μ΄μ „μœΌλ‘œ λŒμ•„κ°‘λ‹ˆλ‹€.

μ€‘μš”ν•œ 것은 깊게 νƒμƒ‰ν•˜κ³  λ‚˜μ„œ μ΄μ „κ³Όμ •μœΌλ‘œ λŒμ•„κ°€μ•Ό ν•œλ‹€λŠ” 점 μž…λ‹ˆλ‹€.

 

 DFSλŠ” μž¬κ·€(μŠ€νƒ)λ₯Ό ν™œμš©ν•΄ κ΅¬ν˜„ν•˜λŠ” κ²½μš°κ°€ λ§ŽμŠ΅λ‹ˆλ‹€. 즉, λ°©λ¬Έν•  수 μžˆλŠ” 지점이 μžˆλ‹€λ©΄ κ·Έ 지점을 λ°©λ¬Έν•˜λŠ” ν•¨μˆ˜λ₯Ό μž¬κ·€μ μœΌλ‘œ ν˜ΈμΆœν•˜κ³ , 더 이상 λ°©λ¬Έν•  곳이 μ—†λ‹€λ©΄ ν•¨μˆ˜λ₯Ό μ’…λ£Œν•˜λ©΄ 될 κ²ƒμž…λ‹ˆλ‹€.

 

λ‹€λ§Œ, 이미 λ°©λ¬Έν–ˆλ˜ 지점을 또 λ°©λ¬Έν•˜λ©΄ 효율이 떨어지기 λ•Œλ¬Έμ— 이전에 λ°©λ¬Έν–ˆλ˜ 지점은 λ‹€μ‹œ λ°©λ¬Έν•˜μ§€ μ•Šμ•„μ•Ό ν•©λ‹ˆλ‹€.

ν•œ 번 λ°©λ¬Έν•œ 지점은 μ–΄λ–€ 처리λ₯Ό ν•΄μ„œ 더 이상 λ°©λ¬Έν•˜μ§€ μ•Šλ„λ‘ 막아야 ν•œλ‹€λŠ” κ²ƒμž…λ‹ˆλ‹€.

κ·Έλž˜μ„œ μš°λ¦¬λŠ” visitedλΌλŠ” 배열을 ν•˜λ‚˜ λ§Œλ“€κ³ , κ·Έ 번호의 지점을 λ°©λ¬Έν•œ 적이 μžˆλŠ”μ§€ ν™•μΈν•˜λ©° 진행해야 ν•©λ‹ˆλ‹€.

 

DFS μ˜ˆμ‹œμ½”λ“œ (γ…Šγ…Š μ½”λ“œνŠΈλ¦¬)

 

 

BFSλŠ” Breadth First Search, λ„ˆλΉ„ μš°μ„  νƒμƒ‰μž…λ‹ˆλ‹€.

μž¬κ·€(μŠ€νƒ)을 ν™œμš©ν–ˆλ˜ DFS와 달리, BFSλŠ” 큐λ₯Ό μ‚¬μš©ν•©λ‹ˆλ‹€.

ν•˜λ‚˜μ˜ λ…Έλ“œμ— λ°©λ¬Έν•˜κ²Œ 되면, κ·Έ λ…Έλ“œμ™€ μΈμ ‘ν•œ λ…Έλ“œ 쀑 λ°©λ¬Έν•œ 적이 μ—†λŠ” λ‹€λ₯Έ λ…Έλ“œλ₯Ό λͺ¨λ‘ 큐에 λ„£μŠ΅λ‹ˆλ‹€.

μš°λ¦¬λŠ” 큐가 FIFO κ΅¬μ‘°λΌλŠ” 것을 μ•ŒκΈ° λ•Œλ¬Έμ—, μ΄λŸ°μ‹μœΌλ‘œ λ„£κ²Œ 되면 이후엔 처음 λ„£μ—ˆλ˜ λ…Έλ“œμ˜ 이웃 λ…Έλ“œλ₯Ό 순차적으둜 λ°©λ¬Έν•˜κ²Œ 될 κ²ƒμž…λ‹ˆλ‹€.

 

μžμ—°μŠ€λŸ½κ²Œ μ΄ν›„μ—λŠ” 각각의 이웃듀을 큐에 λ„£κ²Œ 될텐데, μ΄λŸ°μ‹μœΌλ‘œ μ§„ν–‰λ˜λ©΄

μ‹œμž‘ λ…Έλ“œμ˜ 이웃 -> κ·Έ λ‹€μŒ λ…Έλ“œμ˜ 이웃 -> κ·Έ λ‹€μŒ λ‹€μŒ λ…Έλ“œμ˜ 이웃

순으둜 λ°©λ¬Έν•˜κ²Œ 될 κ²ƒμž…λ‹ˆλ‹€. 즉, μ‹œμž‘μ μ„ κΈ°μ€€μœΌλ‘œ κ°€μž₯ κ°€κΉŒμš΄ 정점뢀터 λ°©λ¬Έν•˜κ²Œ λ˜λŠ” κ²ƒμž…λ‹ˆλ‹€.

 

BFS κ³Όμ • μ˜ˆμ‹œ (좜처 μ½”λ“œνŠΈλ¦¬)

 

 

κ·Έλ ‡λ‹€λ©΄ DFS와 BFS의 μ„±λŠ₯ μ°¨μ΄λŠ”?

결둠만 λ§ν•˜λ©΄ 이둠적으둠 별 차이 μ—†λ‹€κ³  ν•©λ‹ˆλ‹€.

 

μ–΄μ°¨ν”Ό λͺ¨λ“  λ…Έλ“œμ™€ 엣지λ₯Ό λ°©λ¬Έν•˜λŠ” 것이기 λ•Œλ¬Έμ— μ‹œκ°„λ³΅μž‘λ„ μžμ²΄λŠ” λ‘œ λ™μΌν•©λ‹ˆλ‹€.

κ·ΈλŸ¬λ‚˜ μ‹€μ œλ‘œ μ½”λ“œλ₯Ό 짜게되면 DFSκ°€ μ•½κ°„ 느린 편인데, κ·Έ μ΄μœ λŠ” μž¬κ·€ν•¨μˆ˜μ˜ μ˜€λ²„ν—€λ“œ(ν•¨μˆ˜ μ‹€ν–‰ μ‹œ λ°œμƒν•˜λŠ” μ‹œκ°„ 지연) λ•Œλ¬Έμž…λ‹ˆλ‹€.

ν•˜μ§€λ§Œ 큰 λ¬Έμ œλŠ” μ—†κΈ° λ•Œλ¬Έμ—, 상황에 따라 더 νŽΈν•œ μ•Œκ³ λ¦¬μ¦˜μ„ μ„ νƒν•΄μ„œ μ‚¬μš©ν•˜λ©΄ λ©λ‹ˆλ‹€.

 

보톡 μ΅œλ‹¨κ±°λ¦¬λ₯Ό κ΅¬ν•˜λŠ” λ¬Έμ œμ—λŠ” BFSλ₯Ό μ‚¬μš©ν•©λ‹ˆλ‹€.

BFSλŠ” μ •μ˜μƒ μ‹œμž‘μ μœΌλ‘œλΆ€ν„° κ°€κΉŒμš΄ 지점뢀터 λ°©λ¬Έν•˜κ²Œ 되기 λ•Œλ¬Έμ—

κ°€μ€‘μΉ˜κ°€ μ „λΆ€ λ™μΌν•œ κ·Έλž˜ν”„μ—μ„œλŠ” μ΅œλ‹¨κ±°λ¦¬λ₯Ό ν™•μ‹€ν•˜κ²Œ ꡬ해쀄 수 μžˆλŠ” κ²ƒμž…λ‹ˆλ‹€.

 

 

좜처 μ½”λ“œνŠΈλ¦¬
728x90