[프로그래머스 레벨3] 가장 먼 노드 [Javascript/ BFS]

문제 유형 : BFS

https://school.programmers.co.kr/learn/courses/30/lessons/49189

프로그래머스

 

문제 풀이

그래프 문제 (노드, 간선, 최단경로 키워드)
최단 경로가 제일 큰 경우의 집합을 구하는 문제입니다.

그래프를 연결리스트로 구현했습니다.

최단 거리 문제이기 때문에 BFS 알고리즘을 사용했습니다.

 

 

전체 코드

function solution (n, edge){
    const graph = Array.from(Array(n+1), () => [])
    
    // 문제 : 간선은 양방향 (둘 다 갈 수 있다)
    for (const [a, b] of edge){
        graph[a].push(b);
        graph[b].push(a); // graph[b].push(a); 처음에 오타 못찾아서 밑에 코드 안 들어감
    }
    //console.log(graph)
    //	[ [], [ 3, 2 ], [ 3, 1, 4, 5  ], [6, 4, 2, 1 ], [ 3, 2 ], [ 2 ], [ 3 ] ]
    
    const distance = Array(n+1).fill(0);
    distance[1] = 1
    
    // BFS : 너비우선 탐색, 가까이 있는거 먼저 탐색
    const queue = [1];
    while(queue.length > 0){
        const start = queue.shift(); // shift는 O(n)이지만 요소가 적을 경우에는 자바스크립트에서 최적화를 해준다.
        // dest : 목적지
        for(const dest of graph[start]){
            if(distance[dest] === 0) { // 이미 가지 않은 경우엔 0으로 초기화가 되어있다
                queue.push(dest);
                distance[dest] = distance[start] + 1 
            }
        }
    }
    
    // 내림차순 정렬
    distance.sort((a,b) => b-a);
    // filte 배열 반환
    const lenarr = distance.filter((it) => it === distance[0])
    return lenarr.length;
    //console.log(distance)
    //   [
    //   0, 1, 2, 2,
    //   3, 3, 3
    // ]
}