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

BFS1

[๊ทธ๋ž˜ํ”„] ๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰ BFS & ๊นŠ์ด์šฐ์„ ํƒ์ƒ‰ DFS ๋ชจ๋“  ์ •์ ์„ ๋ฐฉ๋ฌธํ•˜๋Š” ๋ฐฉ๋ฒ• : ๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰ BFS, ๊นŠ์ด์šฐ์„ ํƒ์ƒ‰ DFS ๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰ BFS ๋จผ์ € ๋ฃจํŠธ์˜ ์ž์‹์„ ์ฐจ๋ก€๋กœ ๋ฐฉ๋ฌธํ•จ ๋‹ค์Œ์œผ๋กœ ๋ฃจํŠธ ์ž์‹์˜ ์ž์‹, ๋ฃจํŠธ์—์„œ 2๊ฐœ์˜ ๊ฐ„์„ ์„ ๊ฑฐ์ณ์„œ ๋„๋‹ฌํ•  ์ˆ˜ ์žˆ๋Š” ์ •์  ๋ฐฉ๋ฌธ ๋ฃจํŠธ๋กœ๋ถ€ํ„ฐ 3๊ฐœ์˜ ๊ฐ„์„ ์„ ๊ฑฐ์ณ์„œ ๋„๋‹ค๋ž—๋Š” ์ •์ ๋“ค 4๊ฐœ, 5๊ฐœ... ์ˆœ์œผ๋กœ ๋ฐฉ๋ฌธํ•จ ๊นŠ์ด์šฐ์„ ํƒ์ƒ‰ DFS ๋ฃจํŠธ ์ž์‹ ์ •์ ์„ ํ•˜๋‚˜ ๋ฐฉ๋ฌธํ•œ ๋‹ค์Œ, ์•„๋ž˜๋กœ ๋‚ด๋ ค๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๊ณณ๊นŒ์ง€ ๋‚ด๋ ค๊ฐ ๋” ์ด์ƒ ๋‚ด๋ ค๊ฐˆ ์ˆ˜๊ฐ€ ์—†์œผ๋ฉด ์œ„๋กœ ๋˜๋Œ์•„์˜ค๋‹ค๊ฐ€ ๋‚ด๋ ค๊ฐˆ ๊ณณ์ด ์žˆ์œผ๋ฉด ์ฆ‰๊ฐ ๋‚ด๋ ค๊ฐ BFS๋Š” ์˜†์œผ๋กœ ์ญ‰ ํ›‘์–ด ๋‚˜๊ฐ€๊ณ , DFS๋Š” ์•„๋ž˜๋กœ(๊นŠ์ด) ๊ฐˆ ์ˆ˜ ์žˆ๋Š” ๋ฐ๊นŒ์ง€ ๊ฐ”๋‹ค๊ฐ€ ๋ง‰ํžˆ๋ฉด ๋˜๋Œ์•„์™€์„œ ๋‹ค์‹œ ๋‚ด๋ ค๊ฐ DFS์— ๊ธฐ๋ฐ˜ํ•œ ํƒ์ƒ‰ ๋ฐฉ๋ฒ•์„ ๋ฐฑํŠธ๋ž˜ํ‚น ์ด๋ผ๊ณ  ๋ถ€๋ฅด๊ธฐ๋„ ํ•จ BFS ์ˆ˜ํ–‰ ์ˆœ์„œ ์‹œ์ž‘ ์ •์ ์œผ๋กœ ์ •ํ•ด์ง„ ์ •์ ์„ ๋ฐฉ๋ฌธ(1๋กœ ํ‘œ์‹œ) ์ •์  1์— .. 2023. 12. 8.

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