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

 

 

문제

 

입력값으로 인접행렬인 2차원 배열과 시작정점(from), 도착정점(to)가 주어진다. from 정점으로 부터 to 정점까지 갈 수 있는 경우의 수가 존재하는지 boolan 값으로 반환하라.

 

예시

const result = getDirections(
	[
		[0, 1, 0, 0],
		[0, 0, 1, 0],
		[0, 0, 0, 1],
		[0, 1, 0, 0],
	],
	0,
	2
);

 

위의 예시를 그림으로 시각화 하면 아래와 같다.

 

소스코드 구현

 

이번 문제는 전형적인 BFS(Breadth-First-Seach) 알고리즘 문제다. 주어진 인접행렬의 from 정점부터 시작해서 가능한 모든 정점을 queue에 저장 한 후 queue의 요소들을 순회하면서 최종 도착지점까지의 길이 존재하는지 확인할 수 있다.

 

① 연결 가능한 정점을 담을 Queue, 방문한 지점을 체크할 1차원 배열을 생성한다.

② 최초 Queue에 담을 요소를 주어진 from에서 부터 필터링하여 Queue에 저장한다.(enqueue)

③ Queue의 길이가 0이 될 때 까지 while문을 순회한다. BFS 알고리즘에서는 일반적으로 while문으로 반복을 돌린다.

④ Queue의 첫번째 요소를 pop 한다.(dequeue) 출력된 요소를 visit 했으므로 visitArr[temp]는 true로 변경한다. 출력된 temp 요소가 우리의 최종 도착지점인 to인지 확인한다. 만약 to라면 true를 반환하고 종료한다.

⑤ 주어진 인접행렬의 temp열을 순회한다. temp에서 연결가능한 지점을 찾는 과정이다.

⑥ 방문하지 않았으며 temp에서 연결된 정점이 존재하는 경우 Queue에 요소를 추가한다.(enqueue)

⑦ while 문으로 모든 경우의 수를 다 순회했음에도 도착 정점(to)로 가는 길이 존재하지 않는 경우 false를 반환하고 프로그램을 종료한다.

 

function getDirections(matrix, from, to) {
    
    const queue = [];
    const visitArr = new Array(matrix.length).fill(false);

    for(let i=0; i<matrix[from].length; i++){
        if(matrix[from][i]===1) queue.push(i);
    }

    while(queue.length >0){
        const temp =  queue.shift();
        visitArr[temp] = true;
        if(temp === to) return true;

        for(let i=0; i<matrix[temp].length; i++){
            if(!visitArr[i] && matrix[temp][i]){
                queue.push(i);
            }
        }
    }

    return false;
}

 

 

정리

 

그래프 자료구조에서 인접 행렬은 굉장히 많이 쓰인다. 특히 BFS 알고리즘을 통해 최단거리 길을 구하는 문제에서는 많이 사용된다. 전체 매트릭스의 길이만 주어진 경우 인접행렬을 임의로 생성해서 사용하기도 한다.

 

BFS 알고리즘은 한 정점에서 연결가능한 모든 경우의 수를 검색하면서 낮은 Level의 노드로 이동하는 방식이다. BFS와 다르게 DFS는 가장 낮은 LEVEL에 위한 단말 노드까지 검색을 진행 한 후 한 단계씩 상승하면서 검색하는 방식이다. 

 

BFS 알고리즘은 일반적으로 Queue 자료구조를 사용한다. while문으로 queue의 길이가 0이상인 조건 위에서 queue를 enqueue / dequeue 하는 방식으로 순회한다. 모든 문제가 이 방식으로 풀리는 건 아니지만, BFS의 가장 기본적인 구조를 알아봤다.

 

 

 

 

 

[Algorithm] 시간복잡도 개선 부분집합 문제

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

 

[Algorithm] Javascript 인접 행렬(Adjacency Matrix) 생성하기