๐ DFS (Depth-First Search)
DFS๋ ๊น์ด ์ฐ์ ํ์์ด๋ผ๊ณ ๋ ๋ถ๋ฅด๋ฉฐ, ๊ทธ๋ํ์์ ๊น์ ๋ถ๋ถ์ ์ฐ์ ์ ์ผ๋ก ํ์ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
DFS๋ ์คํ ์๋ฃ๊ตฌ์กฐ(ํน์ ์ฌ๊ทํจ์)๋ฅผ ์ด์ฉํ๋ฉฐ, ๊ตฌ์ฒด์ ์ธ ๋์ ๊ณผ์ ์ ๋ค์๊ณผ ๊ฐ๋ค.
- ํ์ ์์ ๋
ธ๋๋ฅผ ์คํ์ ์ฝ์
ํ๊ณ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ.
- ์คํ์ ์ต์๋จ ๋
ธ๋์ ๋ฐฉ๋ฌธํ์ง ์์ ์ธ์ ํ ๋
ธ๋๊ฐ ํ๋๋ผ๋ ์์ผ๋ฉด ๊ทธ ๋
ธ๋๋ฅผ ์คํ์ ๋ฃ๊ณ ๋ฐฉ๋ฌธ์ฒ๋ฆฌ. ๋ฐฉ๋ฌธํ์ง ์์ ์ธ์ ๋
ธ๋๊ฐ ์์ผ๋ฉด ์คํ์์ ์ต์๋จ ๋
ธ๋๋ฅผ ๊บผ๋.
- ๋ ์ด์ 2๋ฒ์ ๊ณผ์ ์ ์ํํ ์ ์์ ๋ ๊น์ง ๋ฐ๋ณต
๋ค์์ ๊ทธ๋ํ๋ฅผ DFS๋ก ํ์ํด๋ณธ๋ค๊ณ ๊ฐ์ ํ์.(๋ฐฉ๋ฌธ ์์๋ 1๋ฒ๋ถํฐ ์์ํ์ฌ ์ธ์ ํ ๋
ธ๋์ค ๋ฒํธ๊ฐ ๋ฎ์ ๋
ธ๋๋ฅผ ๋ฐฉ๋ฌธ)

ํ์ ์์ : 1โ 2 โ 7 โ 6 โ 8 โ 3 โ 4 โ 5
- ์์ ๊ณผ์ ์ ๋ฌธ์ ์ ์ฝ๋๋ก ๊ตฌํํด๋ณธ๋ค๋ฉด?
๐ BFS (Breadth-First Search)
BFS๋ ๋๋น ์ฐ์ ํ์์ด๋ผ๊ณ ๋ ๋ถ๋ฅด๋ฉฐ, ๊ทธ๋ํ์์ ๊ฐ๊น์ด ๋
ธ๋๋ถํฐ ์ฐ์ ์ ์ผ๋ก ํ์ํ๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
BFS๋ ํ ์๋ฃ๊ตฌ์กฐ๋ฅผ ์ด์ฉํ๋ฉฐ, ๊ตฌ์ฒด์ ์ธ ๋์ ๊ณผ์ ์ ๋ค์๊ณผ ๊ฐ๋ค.
- ํ์ ์์ ๋
ธ๋๋ฅผ ํ์ ์ฝ์
ํ๊ณ ๋ฐฉ๋ฌธ ์ฒ๋ฆฌ๋ฅผ ํ๋ค.
- ํ์์ ๋
ธ๋๋ฅผ ๊บผ๋ธ ๋ค์ ํด๋น ๋
ธ๋์ ์ธ์ ๋
ธ๋ ์ค์์ ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋๋ฅผ ๋ชจ๋ ํ์ ์ฝ์
ํ๊ณ ๋ฐฉ๋ฌธ์ฒ๋ฆฌํ๋ค.
- ๋ ์ด์ 2๋ฒ์ ๊ณผ์ ์ ์ํํ ์ ์์ ๋ ๊น์ง ๋ฐ๋ณตํ๋ค.