(1240) 노드사이의 거리

문제

N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리(10,000 이하의 정수)를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

---

문제 풀이

해당 문제는 트리 구조로 해결 할 수 있는 문제이다. 

 

각 노드의 간선마다 가중치를 가지고 있으며, 해당 노드 다음으로 넘어가면 해당 가중치를 더 해주면서 움직이면 되는 문제이다. 아래는 트리에서 가중치를 표시한 트리이다. 

 

매번 root 값이 변경이 되므로 해당 트리는 1 - 2 노드로 넘어 가는 기준으로 파악 하면 쉽니다. 현재 1 - 2로 넘어가는 간선의 가중치는 2 이므로 2를 반환해주면 된다. 

 

 3- 2 로 넘어가는 가중치는 2 + 3 + 2 이므로 7이라는 값을 반환해주면 된다. 

 

---

나의 답안

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {
    static int n, q;
    static List<Node>[] graph;

    static class Node{
        int node;
        int weight;

        public Node(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        q = sc.nextInt();

        graph = new ArrayList[n + 1];

        for (int i = 0; i < n + 1; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            int w = sc.nextInt();

            graph[u].add(new Node(v, w));
            graph[v].add(new Node(u, w));
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for (int i = 0; i < q; i++) {
            int start = sc.nextInt();
            int target = sc.nextInt();
            int bfs = bfs(start, target);

            bw.write( bfs+ "\n");
        }

        bw.flush();
        bw.close();

    }

    private static int bfs(int node, int target) {
        boolean[] visited = new boolean[n + 1];
        int[] sumWeight = new int[n + 1];

        Queue<Integer> queue = new LinkedList<>();

        visited[node] = true;
        queue.add(node);

        while (!queue.isEmpty()) {
            int cur = queue.poll();

            for(Node next : graph[cur]) {

                int nextNode = next.node;
                int nextWeight = next.weight;

                if (!visited[nextNode]) {
                    visited[nextNode] = true;
                    sumWeight[nextNode] = sumWeight[cur] + nextWeight;
                    queue.offer(nextNode);
                }
            }
        }

        return sumWeight[target];
    }


}