๐Ÿ“Œ DFS (Depth-First Search)


DFS๋Š” ๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰์ด๋ผ๊ณ ๋„ ๋ถ€๋ฅด๋ฉฐ, ๊ทธ๋ž˜ํ”„์—์„œ ๊นŠ์€ ๋ถ€๋ถ„์„ ์šฐ์„ ์ ์œผ๋กœ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

DFS๋Š” ์Šคํƒ ์ž๋ฃŒ๊ตฌ์กฐ(ํ˜น์€ ์žฌ๊ท€ํ•จ์ˆ˜)๋ฅผ ์ด์šฉํ•˜๋ฉฐ, ๊ตฌ์ฒด์ ์ธ ๋™์ž‘ ๊ณผ์ •์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

  1. ํƒ์ƒ‰ ์‹œ์ž‘ ๋…ธ๋“œ๋ฅผ ์Šคํƒ์— ์‚ฝ์ž…ํ•˜๊ณ  ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ.
  2. ์Šคํƒ์˜ ์ตœ์ƒ๋‹จ ๋…ธ๋“œ์— ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ธ์ ‘ํ•œ ๋…ธ๋“œ๊ฐ€ ํ•˜๋‚˜๋ผ๋„ ์žˆ์œผ๋ฉด ๊ทธ ๋…ธ๋“œ๋ฅผ ์Šคํƒ์— ๋„ฃ๊ณ  ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌ. ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ์ธ์ ‘ ๋…ธ๋“œ๊ฐ€ ์—†์œผ๋ฉด ์Šคํƒ์—์„œ ์ตœ์ƒ๋‹จ ๋…ธ๋“œ๋ฅผ ๊บผ๋ƒ„.
  3. ๋” ์ด์ƒ 2๋ฒˆ์˜ ๊ณผ์ •์„ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์—†์„ ๋•Œ ๊นŒ์ง€ ๋ฐ˜๋ณต

๋‹ค์Œ์˜ ๊ทธ๋ž˜ํ”„๋ฅผ DFS๋กœ ํƒ์ƒ‰ํ•ด๋ณธ๋‹ค๊ณ  ๊ฐ€์ •ํ•˜์ž.(๋ฐฉ๋ฌธ ์ˆœ์„œ๋Š” 1๋ฒˆ๋ถ€ํ„ฐ ์‹œ์ž‘ํ•˜์—ฌ ์ธ์ ‘ํ•œ ๋…ธ๋“œ์ค‘ ๋ฒˆํ˜ธ๊ฐ€ ๋‚ฎ์€ ๋…ธ๋“œ๋ฅผ ๋ฐฉ๋ฌธ)

๊ทธ๋ž˜ํ”„.PNG

ํƒ์ƒ‰ ์ˆœ์„œ : 1โ†’ 2 โ†’ 7 โ†’ 6 โ†’ 8 โ†’ 3 โ†’ 4 โ†’ 5

๐Ÿ“Œ BFS (Breadth-First Search)


BFS๋Š” ๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰์ด๋ผ๊ณ ๋„ ๋ถ€๋ฅด๋ฉฐ, ๊ทธ๋ž˜ํ”„์—์„œ ๊ฐ€๊นŒ์šด ๋…ธ๋“œ๋ถ€ํ„ฐ ์šฐ์„ ์ ์œผ๋กœ ํƒ์ƒ‰ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด๋‹ค.

BFS๋Š” ํ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์ด์šฉํ•˜๋ฉฐ, ๊ตฌ์ฒด์ ์ธ ๋™์ž‘ ๊ณผ์ •์€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

  1. ํƒ์ƒ‰ ์‹œ์ž‘ ๋…ธ๋“œ๋ฅผ ํ์— ์‚ฝ์ž…ํ•˜๊ณ  ๋ฐฉ๋ฌธ ์ฒ˜๋ฆฌ๋ฅผ ํ•œ๋‹ค.
  2. ํ์—์„œ ๋…ธ๋“œ๋ฅผ ๊บผ๋‚ธ ๋’ค์— ํ•ด๋‹น ๋…ธ๋“œ์˜ ์ธ์ ‘ ๋…ธ๋“œ ์ค‘์—์„œ ๋ฐฉ๋ฌธํ•˜์ง€ ์•Š์€ ๋…ธ๋“œ๋ฅผ ๋ชจ๋‘ ํ์— ์‚ฝ์ž…ํ•˜๊ณ  ๋ฐฉ๋ฌธ์ฒ˜๋ฆฌํ•œ๋‹ค.
  3. ๋” ์ด์ƒ 2๋ฒˆ์˜ ๊ณผ์ •์„ ์ˆ˜ํ–‰ํ•  ์ˆ˜ ์—†์„ ๋•Œ ๊นŒ์ง€ ๋ฐ˜๋ณตํ•œ๋‹ค.