์•Œ๊ณ ๋ฆฌ์ฆ˜

[Algorithm] ๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ - ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ (Breadth-First Search)

jjingle 2024. 2. 20. 14:00

๊ทธ๋ž˜ํ”„ ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰ (BFS; Breadth First Search)
    • ์ •์ ๋“ค๊ณผ ๊ฐ™์€ ๋ ˆ๋ฒจ์— ์žˆ๋Š” ๋…ธ๋“œ๋“ค(ํ˜•์ œ ๋…ธ๋“œ)์„ ๋จผ์ € ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ์‹
    • A - B - C - D - G - H - I - E - F - J
  • ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰ (DFS; Depth First Search)
    • ์ •์ ์˜ ์ž์‹๋“ค์„ ๋จผ์ € ํƒ์ƒ‰ํ•˜๋Š” ๋ฐฉ์‹
    • A - B - D - E - F - C - G - H - I - J