프로그래머스
[프로그래머스] 가장 먼 노드 (javascript, bfs)
해랑쓰
2021. 4. 20. 02:23
728x90
반응형
연결리스트를 만들어준 다음 bfs를 돌면서 각 단계의 큐의 개수로 answer를 업데이트해줬다. (각 단계의 노드 개수)
function solution(n, edge) {
const list={};
for(let i=0;i<edge.length;i++){
let [a,b]=edge[i];
if(list[a]===undefined){
list[a]=[b];
}else{
list[a].push(b);
}
if(list[b]===undefined){
list[b]=[a];
}else{
list[b].push(a);
}
}
const vis=new Array(n+1).fill(false);
const q=[1];
vis[1]=true;
var answer = 0;
while(q.length!=0){
let len=q.length;
answer=len;
for(let i=0;i<len;i++){
let cur=q.shift();
for(let k=0;k<list[cur].length;k++){
let next=list[cur][k];
if(vis[next])continue;
vis[next]=true;
q.push(next);
}
}
}
// console.log(list);
return answer;
}
728x90
반응형