강위찬

재미있는 SW이야기를 소개합니다.

wichan.dev@gmail.com
https://github.com/wichan7

[알고리즘] Javascript로 DFS, BFS구현하기

업데이트:

DFS란?

DFS란 Depth First Search의 약자로 하나의 정점을 깊게 파고들어 탐색하는 방식입니다.
스택을 이용하여 구현할 수 있으며, 재귀 함수의 특징을 통한 구현이 일반적입니다.

BFS란?

BFS란 Breadth First Search의 약자로 DFS처럼 하나의 경로를 깊게 탐색하지 않고 넓게 검사합니다.
큐를 이용하여 구현할 수 있습니다.

구현 전체 코드 (Javascript)

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128

class Queue {
    constructor() {
        this._arr = [];
    }
    enqueue(elem) {
        return this._arr.push(elem);
    }
    dequeue() {
        return this._arr.shift();
    }
    isEmpty() {
        return this._arr.length === 0 ? true : false;
    }
}

function createMap(w, h) {
    let map = [];
    map.__proto__.w = w;
    map.__proto__.h = h;
    map.__proto__.sx = 0;
    map.__proto__.sy = 0;
    map.__proto__.dx = w - 1;
    map.__proto__.dy = h - 1;

    for (let a=0; a<h; a++) {
        let row = [];
        for (let b=0; b<w; b++) {
            row.push( Math.random() < 0.3 ? 0 : 1 );
        }
        map.push(row);
    }

    map[map.sy][map.sx] = 8;
    map[map.dy][map.dx] = 9;

    return map;
}

function printMap(map) {
    let w = map[0].length;
    let h = map.length;

    for (let a=0; a<h; a++) {
        for (let b=0; b<w; b++) {
            process.stdout.write(map[a][b] + " ");
        }
        console.log();
    }
}

function dfs(map) {
    let dfs_do = (y, x) => {
        console.log("=");
        printMap(map);

        // down
        if ( y < map.h - 1 && map[y + 1][x] === 1 ) {
            map[y + 1][x] = 2;
            dfs_do(y + 1, x);
        }
        // right
            if ( y < map.w - 1 && map[y][x + 1] === 1 ) {
                map[y][x + 1] = 2;
                dfs_do(y, x + 1);
            }
        // up
        if ( y > 0 && map[y - 1][x] === 1 ) {
            map[y - 1][x] = 2;
            dfs_do(y - 1, x);
        }
        // left
        if ( x > 0 && map[y][x - 1] === 1 ) {
            map[y][x - 1] = 2;
            dfs_do(y, x - 1);
        }

    }

    dfs_do(map.sy, map.sx);
    return map;
}

function bfs(map) {
    let q = new Queue();
    q.enqueue([map.sy, map.sx]);
    while (!q.isEmpty()) {
        const [y, x] = q.dequeue();
        // escape
        if (map[y][x] === 9) {
            map[y][x] === 2;
            break;
        }

        console.log("=");
        printMap(map);

        // up
        if ( y > 0 && map[y - 1][x] === 1 ) {
            map[y - 1][x] = 2;
            q.enqueue([y - 1, x]);
        }
        // down
        if ( y < map.h - 1 && map[y + 1][x] === 1 ) {
            map[y + 1][x] = 2;
            q.enqueue([y + 1, x]);
        }
        // left
        if ( x > 0 && map[y][x - 1] === 1 ) {
            map[y][x - 1] = 2;
            q.enqueue([y, x - 1]);
        }
        // right
        if ( y < map.w - 1 && map[y][x + 1] === 1 ) {
            map[y][x + 1] = 2;
            q.enqueue([y, x + 1]);
        }
    }
 
    return map;
}

function main() {
    let map = createMap(5, 5);
    dfs(map);
    bfs(map);
}

main();

댓글남기기

참고