1. graph에 객체형식으로 이어지는 노드와 간선의 무게 저장하기

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const V = Number(input[0]);

const graph = Array.from({ length: V + 1 }, () => []);

for (let i = 1; i <= V; i++) {
  const line = input[i].split(" ").map(Number);

  const u = line[0];
  let idx = 1;
  while (true) {
    const v = line[idx++];
    if (v === -1 || v === undefined) break;
    const dist = line[idx++];

    graph[u].push({ to: v, weight: dist });
  }
}

결과

[
  [],
  [ { to: 3, weight: 2 } ],
  [ { to: 4, weight: 4 } ],
  [ { to: 1, weight: 2 }, { to: 4, weight: 3 } ],
  [ { to: 2, weight: 4 }, { to: 3, weight: 3 }, { to: 5, weight: 6 } ],
  [ { to: 4, weight: 6 } ]
]

트러블 슈팅

Q. 어떻게 거리과 정점을 저장할 것인가

JS의 Array는 동적 배열이라 인접 리스트를 구현하기에 매우 편리하지만, 정점이 100,000개일 때는 관리를 잘해야한다.

---

1. Array 안에 Object를 담는 방식 (가독성 중시)

가장 직관적인 방법입니다. 각 인덱스를 정점 번호로 쓰고, 연결된 정보를 객체 { node, dist } 형태로 push 합니다.

// 1번부터 V번까지 정점이 있을 때
const graph = Array.from({ length: V + 1 }, () => []);

// 입력 예시: 1번 노드에 2번 노드(거리 3)가 연결됨
graph[1].push({ to: 2, weight: 3 });

• 장점: edge.to, edge.weight처럼 코드를 읽기 편합니다.
• 단점: 객체 생성 비용이 아주 미세하게 더 발생할 수 있으나, 이 문제의 시간 제한(2초) 안에는 충분히 들어옵니다.

2. TypedArray나 1차원 배열 활용 (메모리 최적화)

만약 메모리 초과가 걱정되거나 더 빠른 성능을 원한다면, 객체 대신 숫자 배열 자체를 넣는 방식입니다.

const graph = Array.from({ length: V + 1 }, () => []);

// [연결노드1, 거리1, 연결노드2, 거리2, ...] 순서로 저장
graph[1].push(2, 3); 

// 꺼내서 쓸 때
for (let i = 0; i < graph[curr].length; i += 2) {
    const nextNode = graph[curr][i];
    const distance = graph[curr][i + 1];
}

• 장점: 객체를 생성하지 않아 가비지 컬렉션(GC) 부담이 적고 메모리 사용량이 줄어듭니다.
• 추천: Node.js로 알고리즘 문제를 풀 때 메모리 제한이 타이트하다면 이 방식이 아주 강력합니다.

1. map(Number)의 중요성: input[i].split(" ")만 하면 요소들이 문자열("3") 상태입니다. 거리 계산을 위해 미리 숫자로 바꿔두는 것이 나중에 편합니다.
2. idx++ 활용: line[idx]를 읽은 직후 바로 ++를 해주면, 다음 요소를 가리키게 되어 코드가 간결해집니다.
3. 메모리 효율: 이 문제는 $V$가 10만이라서 graph[u].push([v, dist])처럼 배열로 넣는 게 객체{}보다 메모리를 조금 더 아낄 수 있습니다. (성능 차이는 미미하지만 메모리 제한이 빡빡할 때 유용한 팁입니다.)

1 2 3 4 5

0 0 0 0 0

0 0 2 0 0

4 0 2 5 0

2. BFS 탐색 함수

임의의 정점에서 간선 탐색 → 방문하지 않았고 가장 거리가 먼 정점 탐색 → 탐색할 정점이 없을 때까지 반복

function BFS(startNode, V, graph) {
  let visited = Array(V + 1).fill(-1); // 방문 리스트 저장 -1: 미방문, 1: 방문
  let distance = Array(V + 1).fill(0); // 가장 먼 노드와의 거리 저장
  let maxWeight = 0;

  let u = startNode;
  visited[startNode] = 1; // 시작 노드에 대해서도 방문 처리
  for (const edge of graph[u]) {
    if (visited[edge.to] === -1) distance[edge.to] = maxWeight + edge.weight; // 미방문 노드에 대해서만 weight 추가
  }
  u = distance.indexOf(Math.max(...arr));
  maxWeight = distance[u];
  visited[u] = 1;
}

이 상태에서 탐색할 정점이 없다는 것을 어떻게 처리할 것인가?

while (queue.length > 0) 조건을 사용

function BFS(startNode, V, graph) {
  let visited = Array(V + 1).fill(false); // 방문 여부만 체크
  let distance = Array(V + 1).fill(0);    // 거리 저장
  let queue = [startNode];                // 탐색할 노드들을 담는 바구니(Queue)

  visited[startNode] = true;

  // 큐에 노드가 들어있는 동안 계속 반복 (더 이상 갈 곳 없으면 자동 종료)
  while (queue.length > 0) {
    let u = queue.shift(); // 현재 노드 꺼내기

    for (const edge of graph[u]) {
      if (!visited[edge.to]) { // 미방문 노드라면
        visited[edge.to] = true;
        distance[edge.to] = distance[u] + edge.weight; // 현재 노드 거리 + 간선 무게
        queue.push(edge.to); // 다음 차례를 위해 큐에 넣기
      }
    }
  }

  // 탐색 종료 후, distance 배열에서 가장 큰 값과 그 인덱스 찾기
  let maxDist = Math.max(...distance);
  let maxNode = distance.indexOf(maxDist);

  return { node: maxNode, dist: maxDist };
}

최종코드

const fs = require("fs");
const input = fs
  .readFileSync(process.platform === "linux" ? "/dev/stdin" : "input.txt")
  .toString()
  .trim()
  .split("\n");

const V = Number(input[0]);

const graph = Array.from({ length: V + 1 }, () => []);

for (let i = 1; i <= V; i++) {
  const line = input[i].split(" ").map(Number);

  const u = line[0]; // 실제 노드 번호를 가져옵니다.
  let idx = 1;
  while (true) {
    const v = line[idx++];
    if (v === -1 || v === undefined) break;
    const dist = line[idx++];

    graph[u].push({ to: v, weight: dist });
  }
}

function BFS(startNode, V, graph) {
  let visited = Array(V + 1).fill(false); // 방문 리스트 저장 -1: 미방문, 1: 방문
  let distance = Array(V + 1).fill(0); // 거리 저장
  let queue = [startNode]; // 탐색할 노드들을 담는 바구니(Queue)

  let u = startNode;
  visited[startNode] = true; // 시작 노드에 대해서도 방문 처리

  // 큐에 노드가 들어있는 동안 계속 반복 (더 이상 갈 곳 없으면 자동 종료)
  while (queue.length > 0) {
    let u = queue.shift(); // 현재 노드 꺼내기

    for (const edge of graph[u]) {
      if (!visited[edge.to]) {
        // 미방문 노드라면
        visited[edge.to] = true;
        distance[edge.to] = distance[u] + edge.weight; // 현재 노드 거리 + 간선 무게
        queue.push(edge.to); // 다음 차례를 위해 큐에 넣기
      }
    }
  }
  let maxDist = Math.max(...distance);
  let maxNode = distance.indexOf(maxDist);

  return { node: maxNode, dist: maxDist };
}

const firstNode = BFS(1, V, graph).node;
const treeRadial = BFS(firstNode, V, graph).dist;

console.log(treeRadial);

🤖 제미나이가 추천해준 코드

function bfs(startNode, V, graph) {
  const dist = new Array(V + 1).fill(-1); // 거리를 저장할 배열, 인덱스에 해당 노드 방문여부 체크
  const queue = [];

  queue.push(startNode);
  dist[startNode] = 0;

  let farthestNode = startNode;
  let maxDist = 0;

  let head = 0;
  while (head < queue.length) {
    const u = queue[head++];

    for (const edge of graph[u]) {
      if (dist[edge.to] === -1) {
        // 방문 안 했으면
        dist[edge.to] = dist[u] + edge.weight;
        queue.push(edge.to);

        // 더 먼 노드를 발견하면 갱신
        if (dist[edge.to] > maxDist) {
          maxDist = dist[edge.to];
          farthestNode = edge.to;
        }
      }
    }
  }
  return { node: farthestNode, dist: maxDist };
}

1. head 변수를 이용한 큐(Queue) 최적화

가장 큰 차이점은 queue.shift() 대신 head 포인터를 사용한 것입니다.

• 이전 로직 (shift()): 배열의 첫 번째 요소를 제거할 때마다 나머지 모든 요소를 한 칸씩 앞으로 당깁니다. 배열 크기가 N일 때 $O(N)$의 시간이 걸려 전체 BFS는 $O(V^2)$이 될 위험이 있습니다.

• 현재 로직 (head++): 요소를 삭제하지 않고 인덱스만 옮깁니다. 이는 $O(1)$의 작업이므로 전체 탐색이 $O(V + E)$로 매우 빠르게 끝납니다. 노드 개수(V)가 10만 개쯤 된다면 이 차이는 어마어마합니다.

2. maxDist와 farthestNode 실시간 갱신

• 이전 로직: BFS가 다 끝난 후 Math.max(...dist)와 indexOf를 사용하여 결과값을 찾았습니다.
• 현재 로직: while문 안에서 새로운 거리를 계산할 때마다 즉시 최댓값을 비교하여 갱신합니다.

차이점: 루프가 끝난 뒤 배열을 다시 전체 순회(V번)할 필요가 없으므로 연산 횟수가 줄어들고 코드가 더 효율적입니다.