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

๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰

์ฝ”๋”ฉํ…Œ์ŠคํŠธ/๊ธฐ๋ณธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ 2022. 2. 20. ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰(BFS) BFS(๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰) 1. BFS(Breadth-First Search)๋ž€? BFS์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰์ด๋ž€ ์˜๋ฏธ๋ฅผ ๊ฐ€์ง„๋‹ค. ์ด๋Š” ๊ฐ€๊นŒ์šด ๋…ธ๋“œ๋ถ€ํ„ฐ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋ž€ ๋œป์ด๋‹ค. DFS๋Š” ์ตœ๋Œ€ํ•œ ๋ฉ€๋ฆฌ์žˆ๋Š”(๊นŠ์€) ๋…ธ๋“œ๋ถ€ํ„ฐ ํƒ์ƒ‰ํ•˜๋Š”๊ฒƒ์— ๋น„ํ•ด BFS๋Š” ๊ฐ€๊นŒ์šด ๋…ธ๋“œ๋ถ€ํ„ฐ ํƒ์ƒ‰ํ•˜๋ฏ€๋กœ ์ด ๋‘๊ฐœ๋ฅผ ์ ์ ˆํ•˜๊ฒŒ ์‚ฌ์šฉํ•ด์•ผ ํ•œ๋‹ค. BFS ๊ตฌํ˜„์—์„œ๋Š” ์„ ์ž…์„ ์ถœ, ์ฆ‰ ํ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์‚ฌ์šฉํ•˜๋Š”๊ฒƒ์ด ์ •์„์ด๋‹ค. BFS ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๋™์ž‘๋ฐฉ์‹์—๋Š” 1. ํƒ์ƒ‰ ์‹œ์ž‘ ๋…ธ๋“œ๋ฅผ ํ์— ์‚ฝ์ž…ํ•˜๊ณ  ๋ฐฉ๋ฌธ ์ฒ˜๋ฆฌ๋ฅผ ํ•œ๋‹ค. 2. ํ์—์„œ ๋…ธ๋“œ๋ฅผ ๊บผ๋‚ด ํ•ด๋‹น ๋…ธ๋“œ์˜ ์ธ์ ‘ ๋…ธ๋“œ ์ค‘์—์„œ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋…ธ๋“œ๋ฅผ ๋ชจ๋‘ ํ์— ์‚ฝ์ž…ํ•˜๊ณ  ๋ฐฉ๋ฌธ ์ฒ˜๋ฆฌ๋ฅผ ํ•œ๋‹ค. 3. 2๋ฒˆ์˜ ๊ณผ์ •์„ ๋” ์ด์ƒ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์—†์„ ๋•Œ๊นŒ์ง€ ๋ฐ˜๋ณตํ•œ๋‹ค. 2. ์˜ˆ์‹œ ์ฝ”๋“œ from collections import d..

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