์ผ | ์ | ํ | ์ | ๋ชฉ | ๊ธ | ํ |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | ||
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 |
- branch ์์ฑ
- ![rejected]
- branch ํ์ธ
- ๋ธ๋์น ํ์ธ
- markdown
- ๋ธ๋์น ์์ฑ
- ๋งํฌ๋ค์ด
- ๋ธ๋์น ์ญ์
- Git๋ช ๋ น์ด
- ์ฝ๋๋ธ๋ญ
- ์ฝ๋๋ธ๋ก
- branch ์ญ์
- Today
- Total
DevLog
TIL(20210723) - BFS & DFS ๋ณธ๋ฌธ
๐ Today
- ๊ทธ๋ํ ํ์ ๊ธฐ๋ฒ ํ์ต
- BFS์ DFS์ ๊ฐ๋ ํ์ต
- BFS์ DFS ๋ฅผ ํ์ฉํ์ฌ ์๊ณ ๋ฆฌ์ฆ ๋ฌธ์ ํ์ด
๐ค Learned
BFS: ๋๋น ์ฐ์ ํ์(Breadth-First Search)
๋๋น ์ฐ์ ํ์(Breadth-first search, BFS)์ ๋งน๋ชฉ์ ํ์ ๋ฐฉ๋ฒ์ ํ๋๋ก ์์ ์ ์ ์ ๋ฐฉ๋ฌธํ ํ ์์ ์ ์ ์ ์ธ์ ํ ๋ชจ๋ ์ ์ ๋ค์ ์ฐ์ ๋ฐฉ๋ฌธํ๋ ๋ฐฉ๋ฒ์ด๋ค. ๋ ์ด์ ๋ฐฉ๋ฌธํ์ง ์์ ์ ์ ์ด ์์ ๋๊น์ง ๋ฐฉ๋ฌธํ์ง ์์ ๋ชจ๋ ์ ์ ๋ค์ ๋ํด์๋ ๋๋น ์ฐ์ ๊ฒ์์ ์ ์ฉํ๋ค.
class Tree{
constructor() {
this.root = null;
}
BFS(fn) { // ์ธ์๋ก callback ํจ์๋ฅผ ๋ฐ๋๋ค.
if(this.root === null) return;
const unvisitedQueue = [this.root];
while(unvisitedQueue.length !== 0){
const current = unvisitedQueue.shift(); // dequeue
unvisitedQueue.push(...current.children); // ํ์ฌ ๋ถ๋ชจ ๋
ธ๋์ ์์๋ค์ ๋ชจ๋ ๋ค ํ์ ๋ด๋๋ค.
fn(current); // ํ์ฌ ๋
ธ๋๋ฅผ ๊ฐ์ง๊ณ callback ํจ์ ์คํ
}
}
}
DFS: ๊น์ด ์ฐ์ ํ์(Depth-First Search)
๊น์ด ์ฐ์ ํ์( depth-first search, DFS)์ ๋งน๋ชฉ์ ํ์ ๋ฐฉ๋ฒ์ ํ๋๋ก ํ์ํธ๋ฆฌ์ ์ต๊ทผ์ ์ฒจ๊ฐ๋ ๋ ธ๋๋ฅผ ์ ํํ๊ณ , ์ด ๋ ธ๋์ ์ ์ฉ ๊ฐ๋ฅํ ๋์์ ์ค ํ๋๋ฅผ ์ ์ฉํ์ฌ ํธ๋ฆฌ์ ๋ค์ ์์ค(level)์ ํ ๊ฐ์ ์์๋ ธ๋๋ฅผ ์ฒจ๊ฐํ๋ฉฐ, ์ฒจ๊ฐ๋ ์์ ๋ ธ๋๊ฐ ๋ชฉํ๋ ธ๋์ผ ๋๊น์ง ์์ ์์ ๋ ธ๋์ ์ฒจ๊ฐ ๊ณผ์ ์ ๋ฐ๋ณตํด ๊ฐ๋ ๋ฐฉ์์ด๋ค.
class Tree {
constructor() {
this.root = null;
}
DFS(fn) {
if(this.root === null) return;
const unvisitedList = [this.root];
while(unvisitedList.length !== 0) {
const current = unvisitedList.shift();
unvisitedList.unshift(...current.children); // list ์์๋ค ๋ฃ์ด์ค๋ค. (์ฐ์ ์์: ๋ด ์์๋ค์ด ๋จผ์ ์ผ! )
fn(current);
}
}
}
์คํ์ฝ๋
const lettersBFS = [];
const lettersDFS = [];
const t = new Tree();
t.root = new Node('a');
t.root.add('b');
t.root.add('d');
t.root.children[0].add('c');
t.BFS(node => lettersBFS.push(node.data));
t.DFS(node => lettersDFS.push(node.data));
์ ๋ฉฐ์น ๊ฐ ์๊ณ ๋ฆฌ์ฆ๋ง ํ์ตํด์ ๊ฐ๋ ๋ค์ด ๋จธ๋ฆฌ ์์์ ๋ค์ฃฝ๋ฐ์ฃฝ ์์ฌ์๋ค
์ฃผ๋ง์ ๋ณต์ต์ ํตํด์ ์ ์ฒด์ ์ผ๋ก ์ ๋ฆฌํ๊ณ ์ดํดํ์ง ๋ชปํ ๋ถ๋ถ๋ค์ ๋ํด์ ๋ค์ ํ์ตํด์ผ๊ฒ ๋ค.
๐ Tomorrow
- ์ฃผ๊ฐ ๋ฐฐ์ด ๋ฒ์ ์ ์ฒด ๋ณต์ต
'๐ค TIL(Today I Learned)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
TIL(20210728) - ๋น๋๊ธฐ(callback, promise, promiseAll, asyncAwait) + fs๋ชจ๋, fetch() (0) | 2021.07.28 |
---|---|
TIL(20210727) - ๋น๋๊ธฐ(callback, promise, asyncAwait) (0) | 2021.07.27 |
TIL(20210722) - ์๋ฃ๊ตฌ์กฐ(Stack, Queue, Tree, Graph) (0) | 2021.07.22 |
TIL(20210720) - ์ฌ๊ท(recursion) (0) | 2021.07.21 |
TIL(20210718) - sort() ๋ฉ์๋ ์ฌ์ฉ๋ฒ (0) | 2021.07.18 |