๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

dfs1

14-3๊ฐ•. ๊ทธ๋ž˜ํ”„์—์„œ์˜ DFS DFS(Depth-First Search) ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ level order traversal (BFS) inorder traversal (DFS) pre-order traversal (DFS) post-order traversal (DFS) 1. ์ถœ๋ฐœ์  s์—์„œ ์‹œ์ž‘ํ•œ๋‹ค. 2. ํ˜„์žฌ ๋…ธ๋“œ๋ฅผ visited๋กœ markํ•˜๊ณ , ์ธ์ ‘ํ•œ ๋…ธ๋“œ๋“ค ์ค‘ unvisited ๋…ธ๋“œ๊ฐ€ ์กด์žฌํ•˜๋ฉด ๊ทธ ๋…ธ๋“œ๋กœ ๊ฐ„๋‹ค. 3. 2๋ฒˆ์„ ๊ณ„์† ๋ฐ˜๋ณตํ•œ๋‹ค. 4. ๋งŒ์•ฝ unvisited์ธ ์ด์›ƒ๋…ธ๋“œ๊ฐ€ ์กด์žฌํ•˜์ง€ ์•Š๋Š” ๋™์•ˆ ๊ณ„์†ํ•ด์„œ ์ง์ „ ๋…ธ๋“œ๋กœ ๋˜๋Œ์•„ ๊ฐ„๋‹ค. 5. ๋‹ค์‹œ 2๋ฒˆ์„ ๋ฐ˜๋ณตํ•œ๋‹ค. 6. ์‹œ์ž‘๋…ธ๋“œ s๋กœ ๋Œ์•„์˜ค๊ณ , ๋”์ด์ƒ ๊ฐˆ ๊ณณ์ด ์—†์œผ๋ฉด ์ข…๋ฃŒํ•œ๋‹ค. ์ด ๊ทธ๋ž˜ํ”„์—์„œ๋Š” 1-3-7-8-7-3-5-2-4-2-5-6 ์ˆœ์„œ๋กœ ๊ฐ„๋‹ค.. (ํ•˜์ง€๋งŒ ์ˆœ์„œ๋Š” ๋ฐ”๋€” ์ˆ˜.. 2020. 12. 6.

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”