๐Ÿ—ฏ๏ธLanguage/Python ๊ฒ€์ƒ‰ ๊ฒฐ๊ณผ

ํ•ด๋‹น ๊ธ€ 13๊ฑด

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