๊ด€๋ฆฌ ๋ฉ”๋‰ด

๋ชฉ๋กDFS (1)

CS Student’s SAP&Tech Journey๐Ÿ’ซ

[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๊นŠ์ด์šฐ์„ ํƒ์ƒ‰(DFS)์ด๋ž€

1. ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ DFS ( Depth - First Search) DFS๋Š” ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰์ด๋ผ๊ณ ๋„ ๋ถ€๋ฅด๋ฉฐ ๊ทธ๋ž˜ํ”„์—์„œ ๊นŠ์€ ๋ถ€๋ถ„์„ ์šฐ์„ ์ ์œผ๋กœ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ž…๋‹ˆ๋‹ค. DFS๋Š” ์Šคํƒ ์ž๋ฃŒ๊ตฌ์กฐ ํ˜น์€ ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•˜๋ฉฐ, ๊ตฌ์ฒด์ ์ธ ๋™์ž‘ ๊ณผ์ •์€ ๋‹ค์Œ๊ณผ ๊ฐ™์Šต๋‹ˆ๋‹ค.ํƒ์ƒ‰ ์‹œ์ž‘ ๋…ธ๋“œ๋ฅผ ์Šคํƒ์— ์‚ฝ์ž…ํ•˜๊ณ  ๋ฐฉ๋ฌธ ์ฒ˜๋ฆฌ๋ฅผ ํ•ฉ๋‹ˆ๋‹ค.์Šคํƒ์˜ ์ตœ์ƒ๋‹จ ๋…ธ๋“œ์— ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ธ์ ‘ํ•œ ๋…ธ๋“œ๊ฐ€ ํ•˜๋‚˜๋ผ๋„ ์žˆ์œผ๋ฉด ๊ทธ ๋…ธ๋“œ๋ฅผ ์Šคํƒ์— ๋„ฃ๊ณ  ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌํ•ฉ๋‹ˆ๋‹ค. ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ธ์ ‘ ๋…ธ๋“œ๊ฐ€ ์—†์œผ๋ฉด ์Šคํƒ์—์„œ ์ตœ์ƒ๋‹จ ๋…ธ๋“œ๋ฅผ ๊บผ๋ƒ…๋‹ˆ๋‹ค.๋”์ด์ƒ 2๋ฒˆ์˜ ๊ณผ์ •์„ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์—†์„ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•ฉ๋‹ˆ๋‹ค. 2. DFS ๋™์ž‘ ์˜ˆ์‹œ (์˜ˆ์‹œ๋Š” ๋ฒˆํ˜ธ๊ฐ€ ๋‚ฎ์€ ์ธ์ ‘ ๋…ธ๋“œ ๋ถ€ํ„ฐ ๋ฐฉ๋ฌธ)[step 0] ๊ทธ๋ž˜ํ”„ ์ค€๋น„ (๋ฐฉ๋ฌธ ๊ธฐ์ค€ : ๋ฒˆํ˜ธ๊ฐ€ ๋‚ฎ์€ ์ธ์ ‘๋…ธ๋“œ๋ถ€ํ„ฐ) / ์‹œ์ž‘๋…ธ๋“œ : 1[step 1..