[Algorithm] Javascript BFS / DFS 알고리즘 문제 기초

How to solve DFS / BFS Alogorithm problem in Javascript?

 

 

문제

 

입력값으로 방향이 없는 간선들의 목록이 주어진다. 연결된 정점의 갯수는 몇개인가?

 

주어진 배열 edges는 시작정점과 도착정점의 정보를 담은 2차원 배열이다. 반환값은 number 타입의 데이터다.

 

예시

 

예를 들어 아래와 같은 입력값이 주어진다고 했을 때 그래프를 시각화 하면 다음과 같다. 따라서 결과값은 3이다.

 

const result = connectedVertices([
	[0, 1],
	[2, 3],
	[4, 5],
]);
console.log(result); // 3

 

 

 

소스 코드 구현

 

그래프 문제는 크게 DFS와 BFS 두가지 알고리즘으로 풀어볼 수 있다. 그 전에 공통적으로 입력받은 2차원 배열을 활용해서 인접 행렬을 생성한다. 

 

 

인접 배열을 생성하기 위해서는 주어진 2차원 배열에서 가장 큰 값을 찾는다.

let max = 0;
edges.forEach((item)=>{
    item.forEach((i)=>{
        if(max < i) max = i;
    })
})

 

배열에서 가장 큰 값을 찾았다면 이를 활용해 방문을 체크할 1차원 배열과 2차원으로 구성된 인접 행렬을 생성한다.

const visit = new Array(max+1).fill(false);
const adjacencyMatrix = new Array(max+1).fill(0).map((item)=>new Array(max+1).fill(0))

for(let i=0; i<edges.length; i++){
    const from = edges[i][0];
    const to = edges[i][1];
    adjacencyMatrix[from][to] = adjacencyMatrix[to][from] = 1;
}

 

인접행렬, 방문 체크 배열를 완성 한 후 두가지 함수를 선언해준다. BFS와 DFS 알고리즘을 활용한 함수다.

 

 

BFS(Breadth First Search)

 

BFS를 사용하는 경우 queue 알고리즘을 사용하기 위한 배열을 생성한다. Queue를 활용해서 현재 정점에 연결된 모든 간선을 검색한 후 연결된 간선이 존재하지 않는 경우 다음 레벨로 넘어가서 서치를 진행한다.

const queue = [];

 

① 새로운 요소를 전달받은 후 queue의 길이 만큼 while문이 실행된다.

② queue에서 새로운 요소를 출력한 후 visit을 체크한다.

③ 인접행렬을 순회하면서 방문하지 않았고, 주어진 요소에서 연결된 지점이 있는 경우 해당 요소를 queue에 삽입 후 방문 체크를 진행한다.

④이 과정이 반복되면서 최종적으로 queue에는 아무런 요소도 남지 않게 되고, 함수가 종료된다. 

⑤ 함수가 종료 되는 시점에서 count를 증가시켜 최종적으로 count를 출력한다. 함수가 종료되는 시점이 인접한 간선이 연결되어 있는 그룹이 끝났다는 의미다.

function bfs(vertex){
    queue.push(vertex);
        while(queue.length > 0){

            const temp = queue.shift();
            visit[temp] = true;
            for(let i=0; i<adjacencyMatrix[temp].length; i++){
                if(adjacencyMatrix[temp][i] && !visit[i]){
                    queue.push(i);
                    visit[i] = true;
                }
            }
        }

}

 

 

DFS(Depth First Search)

 

DFS 알고리즘은 재귀 알고리즘을 사용한다. 단말노드까지 검색을 진행 한 후 재귀 함수가 리턴하면서(콜 스택에서 하나씩 제거해 나가면서) 상위노드를 검색한다. 최종 리턴 지점은 루트 노드에서 값이 반환된다.

 

① 입력받은 요소로 방문 여부를 체크해준다.

② 인접행렬을 순회하면서 방문하지 않은 상태이면서 현재 정점에 연결되어 있는 정점이 있는 경우 재귀 함수를 호출한다.

③ 만약 현재 정점에 연결지점이 존재하지 않거나, 방문한 상태라면 아무런 기능도 수행하지 않고 함수가 종료된다.

 

function dfs(vertex){
    visit[vertex] = true;
    for(let i=0; i<adjacencyMatrix[vertex].length; i++){
        if(!visit[i] && adjacencyMatrix[vertex][i]){
            dfs(i);
        }
    }
}

 

 

전체 소스코드

 

function connectedVertices(edges) {
    // 풀이과정
    /*
        1. 인접행렬을 생성한다.
        2. BFS / DFS 알고리즘으로 풀어간다.
    */

    let max = 0;
    edges.forEach((item)=>{
        item.forEach((i)=>{
            if(max < i) max = i;
        })
    })

    let count=0;
    const queue = [];
    const visit = new Array(max+1).fill(false);
    const adjacencyMatrix = new Array(max+1).fill(0).map((item)=>new Array(max+1).fill(0))

    for(let i=0; i<edges.length; i++){
        const from = edges[i][0];
        const to = edges[i][1];
        adjacencyMatrix[from][to] = adjacencyMatrix[to][from] = 1;
    }

    queue.push(edges[0][0])
        
    edges.flat().forEach((item)=>{
        if(!visit[item]){

            dfs(item);
            
            count++;
        }
    })

    function bfs(vertex){
        queue.push(vertex);
            while(queue.length > 0){

                const temp = queue.shift();
                visit[temp] = true;
                for(let i=0; i<adjacencyMatrix[temp].length; i++){
                    if(adjacencyMatrix[temp][i] && !visit[i]){
                        queue.push(i);
                        visit[i] = true;
                    }
                }
            }

    }

    function dfs(vertex){
        visit[vertex] = true;
        for(let i=0; i<adjacencyMatrix[vertex].length; i++){
            if(!visit[i] && adjacencyMatrix[vertex][i]){
                dfs(i);
            }
        }
    }

    return count;
}

 

정리

 

BFS와 DFS 알고리즘을 사용해서 간단한문제를 해결해 봤다. 구현 과정은 여러 문제를 접하면 자연스럽게 익숙해 질 것이다. 중요한 점은 BFS는 Queue를 사용하고, DFS는 재귀 함수를 사용한다는 것이다.

 

또한 그래프 문제에서 공통적으로 수행해야 하는 부분은 인접행렬을 생성하는 부분이다. 단방향 그래프 혹은 무방향 그래프에 따라서 인접행렬을 생성하는 부분은 조금씩 다르다.

 

그래프 문제를 푸는 경우 BFS와 DFS 알고리즘을 사용해서 푸는 개략적인 방향을 잡고 풀면 수월하게 풀어낼 수 있을 것이다.

① 인접행렬 생성

② DFS || BFS 함수 구현

 

 

 

[Algorithm] Javascript Graph 인접 행렬 길 찾기(BFS 알고리즘 기초 문제)

 

[Algorithm] Javascript Tree 자료구조 구현하기 (소스코드 포함)