[백준] 1240번 : 노드사이의 거리

문제

 

 

접근 방식

이전까지의 트리 문제에서는 각 노드 간의 거리가 1이였다면

이번 문제에서는 노드 간 거리가 서로 다르게 주어진다.

 

그래서 인접 리스트를 만들 때

기존에는 각 각선의 양끝 정점에 대해서만 넣어줬다면

이번에는 정점 간의 거리도 넣어준 후에 탐색만 해주면 된다.

 

풀이

public class Main {

	private static int start, end, result;
	private static boolean[] isVisited;
	private static final ArrayList<ArrayList<Pair>> near = new ArrayList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int x, y, d;

		for (int i = 0; i <= n; i++) {
			near.add(new ArrayList<>());
		}

		for (int i = 1; i < n; i++) {
			st = new StringTokenizer(br.readLine());

			x = Integer.parseInt(st.nextToken());
			y = Integer.parseInt(st.nextToken());
			d = Integer.parseInt(st.nextToken());

			near.get(x).add(new Pair(y, d));
			near.get(y).add(new Pair(x, d));
		}

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			start = Integer.parseInt(st.nextToken());
			end = Integer.parseInt(st.nextToken());
			isVisited = new boolean[n + 1];

			dfs(start, 0);
			sb.append(result).append("\n");
		}

		System.out.println(sb);
	}

	private static void dfs(int cur, int move) {
		isVisited[cur] = true;

		for (Pair pair : near.get(cur)) {
			if (isVisited[pair.node]) continue;
			if (pair.node == end) {
				result = move + pair.dist;
				return;
			}
			dfs(pair.node, move + pair.dist);
		}
	}

	private static class Pair {
		int node;
		int dist;

		public Pair(int node, int dist) {
			this.node = node;
			this.dist = dist;
		}
	}
}