[์๊ณ ๋ฆฌ์ฆ] DFS์ BFS JAVA
ยท
์๊ณ ๋ฆฌ์ฆ
๊น์ด ์ฐ์ ํ์ DFS (Depth-First Search) ์์ ๋
ธ๋ ์ ํ: ํ์์ ์์ํ ๋
ธ๋๋ฅผ ์ ํํฉ๋๋ค.๋
ธ๋ ๋ฐฉ๋ฌธ: ํ์ฌ ๋
ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๊ณ , ๋ฐฉ๋ฌธํ๋ค๊ณ ํ์ํฉ๋๋ค.์ธ์ ๋
ธ๋ ํ์: ํ์ฌ ๋
ธ๋์ ์ธ์ ํ ๋
ธ๋๋ค ์ค ๋ฐฉ๋ฌธํ์ง ์์ ๋
ธ๋๋ก ์ด๋ํฉ๋๋ค.๋ฐ๋ณต: ๋ ์ด์ ๋ฐฉ๋ฌธํ ๋
ธ๋๊ฐ ์์ ๋๊น์ง ์ธ์ ๋
ธ๋๋ก ์ด๋ํ๋ ๊ณผ์ ์ ๋ฐ๋ณตํฉ๋๋ค. ๋ชจ๋ ์ธ์ ๋
ธ๋๋ฅผ ๋ฐฉ๋ฌธํ๋ค๋ฉด, ์ด์ ๋
ธ๋๋ก ๋์๊ฐ์ ๋ค์ ์ธ์ ๋
ธ๋๋ฅผ ํ์ํฉ๋๋ค. DFS์ ํ์ฉ๋ฏธ๋ก ์ฐพ๊ธฐ: DFS๋ ๋ฏธ๋ก ์ฐพ๊ธฐ์ ๊ฐ์ ๊ฒฝ๋ก ํ์ ๋ฌธ์ ์ ์ ์ฉํฉ๋๋ค.์ฌ์ดํด ํ์ง: ๊ทธ๋ํ์์ ์ฌ์ดํด์ด ์กด์ฌํ๋์ง ํ์ธํ ๋ ์ฌ์ฉ๋ฉ๋๋ค.๊ฐ๊ฒฐํฉ ์์ ์ฐพ๊ธฐ: DFS๋ ๊ทธ๋ํ์์ ๊ฐ๊ฒฐํฉ ์์๋ฅผ ์ฐพ๋ ์๊ณ ๋ฆฌ์ฆ์ ๊ธฐ๋ณธ์ด ๋ฉ๋๋ค.์์ ์ ๋ ฌ: ์ ํฅ ๋น์ํ ๊ทธ๋ํ(DAG)์์ ์์ ์ ๋ ฌ์ ์ํ..