문제 이해

트리가 주어진다. 이 때 거리를 알고 싶은 점 (A,B) 쌍이 여러 개 주어진다.

이 때, (A,B) 점 사이의 거리를 구하여 출력하는 문제이다.

---

문제 풀이

가중치가 존재하기는 하지만, 이 문제에서 큰 역할을 하진 않는다.

결국 A ⇒ B 사이의 Edge 개수를 최소화 시켜 가는 길을 찾는 것이고, 가중치는 단지 Edge를 최소화 시켜 가는 길을 찾아 해당 값을 더해주기만 하면 그 역할은 끝난다.

Tree도 그래프의 일종이므로, BFS를 통해 문제를 풀면 바로 해결되는 문제이다.

---

코드

import java.io.*;
import java.util.*;

class Node{
	int to;
	int length;
	
	public Node(int to, int length) {
		this.to = to;
		this.length = length;
	}
}

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N, M;
	static ArrayList<Node>[] nodes;
	static boolean[] visit;
	
	static void bfs(int start, int end) {
        // 일반적 BFS와 동일하다. 설명은 생략하겠다
		Queue<Node> queue = new LinkedList<>();
		
		queue.add(new Node(start,0));
		
		while(!queue.isEmpty()) {
			Node search = queue.poll();
			if(search.to == end) { 
            // 목적지 도달. 길이를 출력한 이후 반복문 종료
				sb.append(search.length).append("\n");
				break;
			}
			if(visit[search.to]) continue;
			
			visit[search.to] = true;
			
			for(Node s:nodes[search.to]) {
				queue.add(new Node(s.to, s.length+search.length));
                // 원래의 BFS는 +1이지만, 이 문제는 가중치가 있으므로 
                // 가중치를 더해주었다
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		M = sc.nextInt();
		
		nodes = new ArrayList[N+1];
		
		for(int i = 1;i<N+1;i++) {
			nodes[i] = new ArrayList<>();
		}
		
		int from, to, length;
		for(int i =0;i<N-1;i++) {
			from = sc.nextInt();
			to = sc.nextInt();
			length = sc.nextInt();
			
			nodes[from].add(new Node(to, length));
			nodes[to].add(new Node(from,length));
		}
		
		for(int i =0;i<M;i++) {
			visit = new boolean[N+1];
			from= sc.nextInt();
			to = sc.nextInt();
			
			bfs(from, to);
		}
		
		System.out.println(sb);
	}

	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과