프로그래머스 - 가장 먼 노드

1. 문제

문제 링크

설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한 사항

• 노드의 개수 n은 2 이상 20,000 이하입니다.
• 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
• vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

입출력 예

n	vertex	return
6	[[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]	3

입출력 예 설명

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

2. 풀이

BFS나 다익스트라의 기본기를 물어보는 문제입니다.
저는 BFS를 이용해서 해결했고 풀이한 방법은 다음과 같습니다.

1. BFS를 이용해 1번 노드에 대해서 다른 노드로 가는 비용을 costs배열에 저장합니다.
2. costs배열의 최댓값(가장 멀리 떨어진 노드와의 거리)을 찾고 그 값을 카운팅합니다.

3. 전체 코드

function solution(n, edge) {
    const [visit, costs, edge_list] = [...Array(n + 1)].reduce(m => {
        m[0].push(0);
        m[1].push(0);
        m[2].push([]);
        return m;
    }, [[], [], []]);
    const q = [];
    
    // 가장 멀리 떨어진 노드와의 거리
    let max = 0;

    // 양방향 인접 리스트 설정
    edge.forEach(([n1, n2]) => {
        edge_list[n1].push(n2);
        edge_list[n2].push(n1);
    });

    q.push([1, 0]);
    visit[1] = 1;

    // BFS 시작
    while (q.length) {
        let [node, cost] = q.shift();

        edge_list[node].forEach(next_node => {
            // 방문하지 않았을 때
            if (!visit[next_node]) {
                const next_cost = cost + 1;
                q.push([next_node, next_cost]);
                costs[next_node] = next_cost;
                max = Math.max(max, next_cost);
                visit[next_node] = 1;
            }
        });
    }
    
    return costs.reduce((m, cost) => m += cost == max ? 1 : 0, 0);
}