BFS/DFS 예제 하나로 보기

알고리즘 개요

Depth first 깊이 우선 탐색

• 깊이(depth)를 하나씩 증가시켜가며, 주어진 조건에 맞는 해를 찾는 방식
• 재귀함수나 스택으로 구현
• 노드(node) 방문시 방문여부를 무조건 검사하여야 한다. ⇒ 아니면 무한루프

---

예제

게임 맵 최단거리 - DFS

function solution(maps) {
    var answer = 0;
    var n=maps[0].length;
    var m=maps.length;
    //var arr=new Array(n).fill(0);
    var check=new Array(m);
    for(var j=0;j<m;j++){
        check[j]=new Array(n).fill(0);
   }
    //var check=new Array(m).fill(arr);
    var sum=[];
    var depth=1;
    //var cnt=0;
    var dx = [-1, 0, 1, 0];
    var dy = [0, 1, 0, -1];
    function dfs(x,y){
        //if(check[x][y]==1) return ;
        if(x===m-1 && y===n-1) sum.push(depth);
        
        else {
            for(var i=0;i<4;i++){
                var _x=x+dx[i];
                var _y=y+dy[i];
                if(_x>=0 && _y>=0 && _x<m && _y<n && maps[_x][_y]==1 
                    && check[_x][_y]===0){
                    check[_x][_y]=1;
                    depth++;
                    dfs(_x,_y);
                    check[_x][_y]=0;
                    depth--;
                }
                
            }
        }

    }  
    dfs(0,0);
    
    if(sum.length) {
        sum.sort();
        answer=sum.shift();
    } else {
        answer = -1;
    }
    
    return answer;
}

• DFS로 하면 효율성에서 시간초과가 난다. 최소 거리를 찾을 때는 DFS보다 BFS가 효율적

---

Bread first 너비 우선 탐색

• 인접한 노드를 먼저 탐색하는 방법
• BFS는 재귀가 아님.
• 보통 Queue를 사용하여 구현, FIRST IN FIRST OUT 원칙으로 탐색
• 가장 빠르거나 짧은 답을 찾을 때, BFS를 사용하면 좋다(속도가 DFS보다 빠름)

BFS 풀이

function solution(maps) {
    var answer = 0;
    var n=maps[0].length;
    var m=maps.length;
    //var arr=new Array(n).fill(0);
    var check=new Array(m);
    for(var j=0;j<m;j++){
        check[j]=new Array(n).fill(0);
   }
    //var check=new Array(m).fill(arr);
    //var sum=[];
    
    var queue=[[0,0]];
    var depth=1;
    //var cnt=0;
    var dx = [-1, 0, 1, 0];
    var dy = [0, -1, 0, 1];
    while(queue.length){
        answer++;
        let size=queue.length;
        for(var i=0;i<size;i++){
            var flag=queue.shift();
            var x=flag[0];
            var y=flag[1];

            if(check[x][y]) continue;
            //if(!check[x][y]){
                //maps[x][y]=0;
            check[x][y]=1;
            if(x===m-1 && y===n-1) return answer;
            for(var j=0;j<4;j++){
                var nx=x+dx[j];
                var ny=y+dy[j];
                if(nx<m && ny<n && nx>=0 && ny>=0){
                    if(!check[nx][ny] && maps[nx][ny]){
                        queue.push([nx,ny]);           
                    }
                }
            }   
        }   
    }
    return -1;
}

• BFS가 효율적 해당 풀이시 100점이 나오는 것을 알 수 있다!