[프로그래머스] Lv3 가장 먼 노드

문제 링크

코드

function solution(n, edge) {  
    const leaf = [];
    const graph = Array.from({length: n + 1}, () => []);
    for (const [v1, v2] of edge) {
        graph[v1].push(v2);
        graph[v2].push(v1);
    }
    
    const queue = [];
    const dist = Array.from({length: n + 1}, () => 0);
    
    queue.push(1);
    dist[1] = 1;
    
    while (queue.length) {
        const v = queue.shift();
        const adjacent = graph[v];
        for ( const nv of adjacent) {
            if (dist[nv] === 0) {
                queue.push(nv);
                dist[nv] = dist[v] + 1;
            }
        }
    }
    const max = Math.max(...dist.map(v => v));
    return dist.filter(v => v === max).length;
}

풀이

BFS를 사용해 풀었다. DFS를 사용할 경우 1-2-3 순서로 갔을때 3의 거리가 2가 되기때문에 최단경로가 되지 않는다.
dist는 0으로 초기화 한후 다른 노드에 방문할때마다 값을 이전 노드에서 1씩 증가시켰다.