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

dfs1

[์•Œ๊ณ ๋ฆฌ์ฆ˜] BFS/DFS (feat. stack, queue) ๊ผญ ํ•„์š”ํ•œ ์ž๋ฃŒ๊ตฌ์กฐ ๊ธฐ์ดˆ BFS/DFS๋ฅผ ๋“ค์–ด๊ฐ€๊ธฐ์— ์•ž์„œ, ๋ฐ์ดํ„ฐ๋ฅผ ํ‘œํ˜„ํ•˜๊ณ  ๊ด€๋ฆฌํ•˜๊ธฐ ์œ„ํ•œ ๊ตฌ์กฐ์— ๋Œ€ํ•ด์„œ ๊ฐ„๋‹จํžˆ ์–˜๊ธฐํ•ด๋ณด๊ณ  ๋„˜์–ด๊ฐ€์ž. Stack ๋ฐ•์Šค ์Œ“๊ธฐ์— ๋น„์œ ํ•  ์ˆ˜ ์žˆ๋‹ค ์„ ์ž…ํ›„์ถœ, ํ›„์ž…์„ ์ถœ ํŒŒ์ด์ฌ์—์„œ ์Šคํƒ์„ ์ด์šฉํ•  ๋•Œ์—๋Š” ๋ณ„๋„์˜ ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ์‚ฌ์šฉํ•  ํ•„์š”๊ฐ€ ์—†๋‹ค. ๊ธฐ๋ณธ ๋ฆฌ์ŠคํŠธ์—์„œ append()์™€ pop() ๋ฉ”์„œ๋“œ๋ฅผ ์ด์šฉํ•˜๋ฉด ์Šคํƒ ์ž๋ฃŒ๊ตฌ์กฐ์™€ ๋™์ผํ•˜๊ธฐ ๋™์ž‘ํ•œ๋‹ค. Queue ๋Œ€๊ธฐ์ค„์— ๋น„์œ ํ•  ์ˆ˜ ์žˆ๋‹ค. ์„ ์ž…์„ ์ถœ ๊ตฌ์กฐ ํŒŒ์ด์ฌ์œผ๋กœ ํ๋ฅผ ๊ตฌํ˜„ํ•  ๋•Œ๋Š” collections ๋ชจ๋“ˆ์—์„œ ์ œ๊ณตํ•˜๋Š” deque ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ํ™œ์šฉํ•˜์ž. deque๋Š” ์Šคํƒ๊ณผ ํ์˜ ์žฅ์ ์„ ๋ชจ๋‘ ์ฑ„ํƒํ•œ ๊ฒƒ์ธ๋ฐ ๋ฐ์ดํ„ฐ๋ฅผ ๋„ฃ๊ณ  ๋นผ๋Š” ์†๋„๊ฐ€ ๋ฆฌ์ŠคํŠธ ์ž๋ฃŒํ˜•์— ๋น„ํ•ด ํšจ์œจ์ ์ด๋ฉฐ queue ๋ผ์ด๋ธŒ๋Ÿฌ๋ฆฌ๋ฅผ ์ด์šฉํ•˜๋Š” ๊ฒƒ๋ณด๋‹ค ๋” ๊ฐ„๋‹จํ•˜๋‹ค. ํ์™€ ๊ฐ™์€ ๊ฒฝ์šฐ push_bac.. 2023. 10. 11.

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