알고리즘 가장 먼 노드 javascript
function solution(n, edges) {
// 각 노드와 연결된 노드들의 목록을 객체로 출력
const connectedNode = edges.reduce((acc, [from,to]) => {
acc[from] = (acc[from] || []).concat(to);
acc[to] = (acc[to] || []).concat(from);
return acc
},{})
// console.log(connectedNode)
/* {
'1': [ 3, 2 ],
'2': [ 3, 1, 4, 5 ],
'3': [ 6, 4, 2, 1 ],
'4': [ 3, 2 ],
'5': [ 2 ],
'6': [ 3 ]
} */
// queue에 있는 node와 연결된 node 탐색 1번부터 시작
let queue = [1];
// 최단거리를 구해야하므로 한번 방문한 노드 재방문 x
let visited = {1: true};
// 노드마다 최단거리를 구해서 객체로 정리
let minDis = {1: 0};
while(queue.length) {
const node = queue.shift()
// queue 노드와 연결된 노드 탐색
connectedNode[node].forEach(e => {
// 방문한 곳이 노드가 아니라면
if(!visited[e]) {
// 방문 했다고 표시
visited[e] = true;
// 노드를 큐에 삽입
queue.push(e);
// 이전노드 + 1이 현재 노드의 최단거리.
// 방문한 노드는 재 방문하지 않기 때문에
// 항상 최단거리가 됨.
minDis[e] = minDis[node] + 1;
}
})
}
// console.log(minDis)
// { '1': 0, '2': 1, '3': 1, '4': 2, '5': 2, '6': 2 }
const dis = Object.values(minDis);
const maxDis = Math.max(...dis);
const answer = dis.filter(e => e === maxDis);
return answer.length;
}
Author And Source
이 문제에 관하여(알고리즘 가장 먼 노드 javascript), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@gytlr01/알고리즘-가장-먼-노드-javascript저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)