[JavaScript] 가장 먼 노드 (BFS 그래프 알고리즘)

프로그래머스 Lv. 3 '가장 먼 노드'

Solved-Algorithm/JavaScript/프로그래머스/3/49189. 가장 먼 노드 at main · ParkBible/Solved-Algorithm

 

거리를 묻는 문제인만큼 전형적인 BFS 포맷으로 풀 수 있는 문제이며, 인접 노드 테이블 대신 간선 좌표를 주기 때문에 변환이 필요하다.

 

 

function solution(n, edge) {
    const graph = {};
    
    // 간선 좌표를 인접 노드 테이블 - {node: [nodes]} 형태로 변환
    for (const [a, b] of edge) {
        if (!graph[a]) graph[a] = [];
        if (!graph[b]) graph[b] = [];

        graph[a].push(b);
        graph[b].push(a);
    }
    // ------

    const table = {};

    const bfs = (graph, start) => {
        const visited = new Set([start]);
        const queue = [[start, 0]];

        while (queue.length > 0) {
            const [node, dist] = queue.shift();

            // 가장 긴 거리인 노드가 뭔지 찾기 위해 테이블 - {dist: [nodes]} 만들기
            if (table[dist]) {
                table[dist].push(node);
            } else {
                table[dist] = [node];
            }
            // ------

            for (const next of graph[node]) {
                if (!visited.has(next)) {
                    queue.push([next, dist + 1]);
                    visited.add(next);
                }
            }
        }
    }

    bfs(graph, 1);

	// 가장 긴 거리가 뭔지 table에서 찾음
    const maxDist = Math.max(...Object.keys(table));

    return table[maxDist].length;
}