DepthFirstSearch

๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰(Depth-First Search)

: ๋ฃจํŠธ ๋…ธ๋“œ(ํ˜น์€ ๋‹ค๋ฅธ ์ž„์˜์˜ ๋…ธ๋“œ)์—์„œ ์‹œ์ž‘ํ•ด์„œ ๋‹ค์Œ ๋ถ„๊ธฐ(branch)๋กœ ๋„˜์–ด๊ฐ€๊ธฐ ์ „์— ํ•ด๋‹น ๋ถ„๊ธฐ๋ฅผ ์™„๋ฒฝํ•˜๊ฒŒ ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ๋ฒ•

๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰(DFS)์˜ ํŠน์ง•

  • ์ž๊ธฐ ์ž์‹ ์„ ํ˜ธ์ถœํ•˜๋Š” ์ˆœํ™˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ํ˜•ํƒœ ๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋‹ค.

  • ์ „์œ„ ์ˆœํšŒ(Pre-Order Traversals)๋ฅผ ํฌํ•จํ•œ ๋‹ค๋ฅธ ํ˜•ํƒœ์˜ ํŠธ๋ฆฌ ์ˆœํšŒ๋Š” ๋ชจ๋‘ DFS์˜ ํ•œ ์ข…๋ฅ˜์ด๋‹ค.

  • ์ด ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌํ˜„ํ•  ๋•Œ ๊ฐ€์žฅ ํฐ ์ฐจ์ด์ ์€, ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰์˜ ๊ฒฝ์šฐ ์–ด๋–ค ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธํ–ˆ์—ˆ๋Š”์ง€ ์—ฌ๋ถ€๋ฅผ ๋ฐ˜๋“œ์‹œ ๊ฒ€์‚ฌ ํ•ด์•ผ ํ•œ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค.

  • ์ด๋ฅผ ๊ฒ€์‚ฌํ•˜์ง€ ์•Š์„ ๊ฒฝ์šฐ ๋ฌดํ•œ๋ฃจํ”„์— ๋น ์งˆ ์œ„ํ—˜์ด ์žˆ๋‹ค.

DFS

Last updated