DevLog

TIL(20210723) - BFS & DFS ๋ณธ๋ฌธ

๐Ÿค” TIL(Today I Learned)

TIL(20210723) - BFS & DFS

Seungjae Lee 2021. 7. 23. 11:48

๐ŸŽ 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

- ์ฃผ๊ฐ„ ๋ฐฐ์šด ๋ฒ”์œ„ ์ „์ฒด ๋ณต์Šต

Comments