노드 사이의 거리

노드사이의 거리

문제 설명

N

$N$

개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

예제 입력

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

예제 출력

2
7

---

문제 풀이

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

const solution = (input) => {
  let idx = 0;
  const [N, M] = input[idx++].split(" ").map(Number);

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

  for (let i = 0; i < N - 1; i++) {
    const [a, b, c] = input[idx++].split(" ").map(Number);
    graph[a].push({ to: b, cost: c });
    graph[b].push({ to: a, cost: c });
  }

  for (let i = 0; i < M; i++) {
    const [start, end] = input[idx++].split(" ").map(Number);

    // const bfs = () => {
    //   const visited = Array.from({ length: N }, () => false);
    //   let queue = [[start, 0]];
    //   visited[start] = true;

    //   let head = 0;
    //   while (queue.length > head) {
    //     const [cur, dist] = queue[head++];

    //     if (cur === end) return dist;

    //     for (const { to, cost } of graph[cur]) {
    //       if (!visited[to]) {
    //         visited[to] = true;
    //         queue.push([to, dist + cost]);
    //       }
    //     }
    //   }
    //   return 0;
    // };
    const visited = Array.from({ length: N }, () => false);
    let answer = 0;
    const dfs = (cur, dist) => {
      if (cur === end) {
        answer = dist;
        return;
      }

      visited[cur] = true;

      for (const { to, cost } of graph[cur]) {
        if (!visited[to]) {
          dfs(to, dist + cost);
        }
      }
    };

    dfs(start, 0);
    console.log(answer);
  }
};
solution(input);

아이디어 / 접근법

1. DFS 혹은 BFS로 그래프 탐색
2. 끝 값에 도달하면 dist 반환
3. 결과값 출력

후기

그냥 BFS, DFS 기본 문제입니다.