99클럽 코테 스터디 17일차 TIL - 너구리 구구(BFS)

문제: https://www.acmicpc.net/problem/18126
알고리즘 분류: 너비 우선 탐색, 깊이 우선 탐색, 그래프 이론, 그래프 탐색, 트리

문제 접근

트리 구조에서 루트(1번 입구)에서 가장 먼 노드를 찾는 문제

입력

4
1 2 3
2 3 2
2 4 4

출력

7

내 코드 (초기)

const fs = require('fs');
const [N, ...edges] = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const numN = Number(N);
const graph = Array.from({ length: numN + 1 }, () => []);

for(let i = 0; i < edges.length; i++){
    const [a, b, c] = edges[i].split(' ').map(Number);
    graph[a].push({ node: b, distance: c });
    graph[b].push({ node: a, distance: c });
}

const findFarthestRoom = (start) => {
    const distances = Array(numN + 1).fill(-1);
    distances[start] = 0;
    
    const queue = [start];
    let maxDistance = 0;
    let farthestRoom = start;
    
    while(queue.length > 0){
        const current = queue.shift();
        for(const {node, distance } of graph[current]){
            if(distances[node] === -1){
                distances[node] = distances[current] + distance;
                queue.push(node);
            }
            // 더 먼 방을 찾으면 업데이트
            if(distances[node] > maxDistance){
                maxDistance = distances[node];
                farthestRoom = node;
            }
        }
    }
    return { maxDistance, farthestRoom };
}

const result = findFarthestRoom(1);
console.log(result.maxDistance);

개선

const fs = require('fs');
const [N, ...edges] = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const numN = Number(N);
const graph = Array(numN + 1).fill().map(()=>[]); // 인접리스틀로 그래프 표현

for(let i = 0; i < edges.length; i++){
    const [a, b, c] = edges[i].split(' ').map(Number);
    graph[a].push([b, c]); // 배열사용: 객체생성 오버헤드 제거
    graph[b].push([a, c]);
}

const findFarthestRoom = (start) => {
    const distances = Array(numN + 1).fill(-1);
    distances[start] = 0;
    
    const queue = [start];
    let maxDistance = 0;
    let farthestRoom = start;
    
    let queueIndex = 0; // shift() 댓신 인덱스 사용 => 성능향상
    
    while(queueIndex < queue.length){
        const current = queue[queueIndex++];
        
        for(const [nextNode, dist] of graph[current]){
            if(distances[nextNode] === -1){
                const newDistance = distances[current] + dist;
                distances[nextNode] = newDistance;
                queue.push(nextNode);
                
                // 더 먼 방을 찾으면 업데이트
                if(newDistance > maxDistance){
                    maxDistance = newDistance;
                    farthestRoom = nextNode;
                }
            }
        }
    }
    return maxDistance;
}
console.log(findFarthestRoom(1));