JS 100제 문제 72 너비 우선 탐색
992 단어 JavaScriptJS100제JS100제
<풀이 코드>
const graph = {
'E': ['D', 'A'],
'F': ['D'],
'A': ['E', 'C', 'B'],
'B': ['A'],
'C': ['A'],
'D': ['E','F']};
/*
bfs는 queue과 방문 여부 확인해서 해결
queue -> FIFO (들어온 순서대로 나감)
*/
function bfs(graph, start){ // 깊이 우선 탐색법
var queue = []; // 빈 스택 배열
var visited = []; // 방문 여부를 확인할 빈 배열
queue.push(start); // 먼저 start할 위치를 담아놓고 시작
while(queue.length!=0){ // queue에서 모두 shift 될 때까지
var n = queue.shift(); // shift -> 배열의 앞에서부터 뽑기 , pop -> 배열의 뒤에서부터 뽑기
if(!visited.includes(n)){ // 방문 여부 확인
visited.push(n);
var x = graph[n].filter(x=>!visited.includes(x)); //처음 n에 연결된 노드 중 방문하지 않은 노드
for(var i in x){
queue.push(x[i]); // queue에 push
}
}
}
return visited; // E D A F C B
}
console.log(bfs(graph,'E'));
Author And Source
이 문제에 관하여(JS 100제 문제 72 너비 우선 탐색), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mjlee/JS-100제-문제-72-너비-우선-탐색저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)