[toc]
1. DFS(๊น์ด ์ฐ์ ํ์)
(1) ์ ์
๊ทธ๋ํ ํ์ ๊ธฐ๋ฒ ์ค ํ๋์ด๋ค.
DFS๋ ์์ ์ ์ ์์ ๊ฐ ์ ์๋ ๋ถ๊ธฐ๋ค ์ค ํ๋๋ฅผ ํํ์ฌ, ํด๋น ๋ถ๊ธฐ์์ ๊ฐ ์ ์๋ ์ต๋ ๊น์ด๊น์ง ํ์ํ ํ, ๋ค์ ๋ถ๊ธฐ๋ก ๋์ด๊ฐ์ ๊ฐ์ ์์
์ ๋ฐ๋ณตํ๋ ์์ ํ์ ๊ธฐ๋ฒ์ด๋ค.
ํด๋น Tree ๊ตฌ์กฐ๋ฅผ DFS๋ก ์ํํ๋ฉด, 1->2->3->4->5->6->7->8->9->10->11->12->13 ์์ผ๋ก ์กฐํํ๋ค.
(2) ์๊ฐ ๋ณต์ก๋
O(V+E)
V: ์ ์ , E: ๊ฐ์
(3) ๊ตฌํ ๋ฐฉ๋ฒ
์ฌ๊ท๋ฅผ ์ด์ฉํด ๊ตฌํํ๋ค. (์ฌ๊ท๊ฐ ๊ฐ์ง๋ stack์ ์ฑ์ง ์ด์ฉ)
๋ฐฉ๋ฌธ๋ฐฐ์ด์ ํ์ฉํ์ฌ, ํ ๋ฒ ๋ฐฉ๋ฌธํ ๋
ธ๋๋ ์ฌ๋ฐฉ๋ฌธํ์ง ์๋ ๊ฒ์ด ํต์ฌ์ด๋ค.
- ์ฌ์ ์ธํ : ๋ฐฉ๋ฌธ ๋ฐฐ์ด ๋ง๋ค๊ธฐ, ๊ทธ๋ํ๋ฅผ ์ธ์ ํ๋ ฌ ํน์ ์ธ์ ๋ฆฌ์คํธ๋ก ํํ
- ์ฌ๊ท ํจ์๋ฅผ ๋ง๋ค์ด DFS ๊ตฌํ
public static void DFS(int now){
// 0. ๊ธฐ์ ์กฐ๊ฑด: ๋ ์ด์ ๋ฐฉ๋ฌธํ ์ ์ ์ด ์์ ๊ฒฝ์ฐ์ ๋ํ ๊ณ์ฐ ํน์ return ์ค์
// 1. ๋ฐฉ๋ฌธ ์ฒดํฌ
isVisited[now] = true;
// 2. ํ์ฌ ์ ์ ์์ ๊ฐ ์ ์๋ ๋
ธ๋๋ค ์ฒดํฌ
for(int i=0; i<lists[now].size(); i++){
Graph next = lists[now].get(i);
// 2-1 ์ฌ๊ท๋ก ๋ค์ ๊น์ด๋ก ๊ฐ๊ธฐ ์ ์ ์ ์ฒ๋ฆฌํ ๋ด์ฉ ์์ฑ
// ...
// 2-2 ๋ค์ ๊น์ด๋ก ์ฌ๊ท
DFS(next);
// 2-3 ํ์ฒ๋ฆฌํ ๋ด์ฉ ์์ฑ
// ...
}
}
2. BFS(๋๋น ์ฐ์ ํ์)
(1) ์ ์
๊ทธ๋ํ ์์ ํ์ ๊ธฐ๋ฒ ์ค ํ๋
์์ ๋
ธ๋์ ๊ฐ๊น์ด ๋
ธ๋๋ถํฐ ์ฐ์ ํ์ํ๋ฉฐ ๋ชจ๋ ๋
ธ๋๋ฅผ ํ์ํ๋ ๋ฐฉ๋ฒ์ด๋ค.
DFS์ ๋น๊ตํด๋ณด๋ฉด ์ฐจ์ด๊ฐ ๋ช
ํํ ๋๊ปด์ง๋ค.
BFS๋ ์์ ๋
ธ๋์ธ 0์์ ์ ์ผ ๊ฐ๊น์ด 1,2,3 ๋จผ์ ํ์ํ ํ, ์ ์ผ ๋จผ์ ํ์ํ๋ 1์ ๊ทผ์ ๋
ธ๋๋ถํฐ ๋ค์ ๋๋น ํ์์ ์ด์ด๋๊ฐ๋ค.
๋ฐ๋ฉด DFS๋ ์ ์ผ ๋จผ์ ๋ง๋ ๋ถ๊ธฐ์ธ 1์ ์์ ๋
ธ๋๋ค๋ถํฐ ๋จผ์ ํ์ํ ํ, ๋ค์ ๋ถ๊ธฐ์ธ 2๋ก ๋์ด๊ฐ๋ค.
โ ํน์ง
BFS๋ ์์ ๋ ธ๋์์ ๊ฐ์ฅ ๊ฐ๊น์ด ๋ ธ๋ ๊ณ์ธต๋ถํฐ ์ฐ์ ํ์ํ๊ธฐ ๋๋ฌธ์, ์์ ๋ ธ๋(A)์์ ํน์ ๋ ธ๋(B)๊น์ง ์ต๋จ ๊ฒฝ๋ก๋ก ๋๋ฌํ๋ ๊ฒ์ ๋ณด์ฅํ๋ค.
(2) ์๊ฐ ๋ณต์ก๋
O(V+E)
V: ์ ์ , E: ๊ฐ์
(3) ๊ตฌํ ๋ฐฉ๋ฒ
์ ์ผ ๊ฐ๊น์ด ์ ์ ์ ๋ฐ๋ก ํ์ํ๋ค. ์ด๋ ์ ์
์ ์ถ์ Queue๋ก ๊ตฌํํ ์ ์๋ค.
DFS์ ๋ง์ฐฌ๊ฐ์ง๋ก, ๋ฐฉ๋ฌธํ๋ ์ ์ ์ ๋ฐฉ๋ฌธํ์ง ์๊ธฐ ์ํด, ๋ฐฉ๋ฌธ ๋ฐฐ์ด์ ํ์๋ก ํ๋ค.
// ๊ทธ๋ํ๋ ์ธ์ ๋ฆฌ์คํธ๋ก ๊ตฌํ...
ArrayList<Integer> [] lists = new ArrayList [N];
// ์
๋ ฅ ๋ฃ๊ธฐ... (์๋ต - ์ธ์ ๋ฆฌ์คํธ๋ก ๊ทธ๋ํ ๊ตฌํ ๋ณด๊ณ ์ค์ธ์!)
ArrayDeque<Integer> aq1 = new ArrayDeque<>();
boolean [] isVisited = new boolean[N];
aq1.add("์์ ์ ์ ");
while(!aq1.isEmpty()){
// ํ์ฌ ๋ฐฉ๋ฌธํ ์ ์ ๊บผ๋ด๊ธฐ
int now = aq1.poll();
// ํ ์ ์ ๊ณผ ๊ทผ์ ํ ์ ์ ๋ค ์ค ๋ฏธ๋ฐฉ๋ฌธ ์ ์ ์ queue์ ๋ฃ๊ธฐ -> queue์ ๋ฃ๋ ์๊ฐ ๋ฐฉ๋ฌธ ์์ ์ด๋ฏ๋ก, ๋ฐฉ๋ฌธ ์ฒ๋ฆฌํ๊ธฐ!
for(int i = 0; i <= lists[now].size(); i++){
int next = lists[now].get(i);
if(!isVisited[next]){
isVisited[next] = true;
aq1.add(next);
}
}
}