알고리즘 가장 먼 노드 javascript

HyosikPark·2021년 1월 22일
0

알고리즘

목록 보기
64/72
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;
}

0개의 댓글