๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๐Ÿ–‹๏ธ ์ž๋ฃŒ๊ตฌ์กฐ์™€ ์•Œ๊ณ ๋ฆฌ์ฆ˜/์•Œ๊ณ ๋ฆฌ์ฆ˜,์ž๋ฃŒ๊ตฌ์กฐ

[๊ทธ๋ž˜ํ”„] ๋„ˆ๋น„์šฐ์„ ํƒ์ƒ‰ BFS & ๊นŠ์ด์šฐ์„ ํƒ์ƒ‰ DFS

by OR15A 2023. 12. 8.

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

 

 

BFS

  • ์ˆ˜ํ–‰ ์ˆœ์„œ
    • ์‹œ์ž‘ ์ •์ ์œผ๋กœ ์ •ํ•ด์ง„ ์ •์ ์„ ๋ฐฉ๋ฌธ(1๋กœ ํ‘œ์‹œ)
    • ์ •์  1์— ์ธ์ ‘ํ•œ ์ •์ ์„ ๋ชจ๋‘ ๋ฐฉ๋ฌธ(2, 3, 4๋กœ ํ‘œ์‹œ)
    • ์ •์  2, 3, 4๋ฅผ ๊ธฐ์ค€์œผ๋กœ ์ธ์ ‘ํ•œ ๋˜๋‹ค๋ฅธ ์ •์ ์ด ์žˆ๋Š”์ง€ ๋ฐฉ๋ฌธ.(5, 6, 7๋กœ ํ‘œ์‹œ)
    • ๋ฐ˜๋ณตํ•˜๋ฉฐ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ •์ ์ด ์—†์–ด์„œ ๋” ์ด์ƒ ๊ฐˆ ๊ณณ์ด ์—†์œผ๋ฉด ๋

 

 

DFS

  • ์ˆ˜ํ–‰ ์ˆœ์„œ
    • ์‹œ์ž‘ ์ •์ ์œผ๋กœ ์ •ํ•ด์ง„ ์ •์ ์„ ๋ฐฉ๋ฌธ(1๋กœ ํ‘œ์‹œ)
    • ์ •์ 1์— ์ธ์ ‘ํ•œ ์ •์  ์ค‘ ํ•˜๋‚˜๋ฅผ ๋ฐฉ๋ฌธ(2๋กœ ํ‘œ์‹œ)
    • ์ •์ 2์— ์ธ์ ‘ํ•˜๋ฉด์„œ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ด 3๊ฐœ์˜ ์ •์  ์ค‘ ํ•˜๋‚˜๋ฅผ ๋ฐฉ๋ฌธํ•จ(3์œผ๋กœ ํ‘œ์‹œ)
    • ์ •์ 3์— ์ธ์ ‘ํ•œ ์ •์  ์ค‘ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ 2๊ฐœ์˜ ์ •์  ์ค‘ ํ•˜๋‚˜๋ฅผ ๋ฐฉ๋ฌธ(4๋กœ ํ‘œ์‹œ)
    • ...์ •์  5๊นŒ์ง€ ๋ฐ˜๋ณต. 5์— ์ธ์ ‘ํ•œ ์ •์  ์ค‘ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ •์ ์ด ์—†์œผ๋ฉด ๋”ฐ๋ผ์„œ ์™”๋˜ ๊ธธ์„ ๋˜๋Œ์•„๊ฐ
    • ๋˜๋Œ์•„๊ฐ€๋Š” ๊ณผ์ •์—์„œ ๋ฐฉ๋ฌธ์—ฌ๋ถ€๋ฅผ ํ™•์ธ. ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ •์ ์ด ์žˆ์œผ๋ฉด ๋ฐฉ๋ฌธํ•œ๋‹ค.
    • ๋˜๋Œ์•„๊ฐ€๋ฉฐ ์‹œ์ž‘ ์ •์ (์ •์ 1)๋กœ ๋„์ฐฉํ•˜๋ฉด ๋” ์ด์ƒ ๊ฐˆ ๊ณณ์ด ์—†์œผ๋ฏ€๋กœ ๋๋‚ธ๋‹ค.

 

 

 

์ฐธ๊ณ ์ž๋ฃŒ : ใ€Œ์‰ฝ๊ฒŒ ๋ฐฐ์šฐ๋Š” ์ž๋ฃŒ๊ตฌ์กฐ with ์ž๋ฐ”ใ€