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

문제 설명

• https://www.acmicpc.net/problem/1240

접는법

• BFS로 문제를 해결할 수 있습니다.

정답

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

public class Main {

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		HashMap<Integer, List<Node>> graph = new HashMap<Integer, List<Node>>();
		for (int i = 0; i < N - 1; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int d = sc.nextInt();
			if (!graph.containsKey(a)) {
				List<Node> temp = new LinkedList<Node>();
				temp.add(new Node(a, b, d));
				graph.put(a, temp);
			} else {
				graph.get(a).add(new Node(a, b, d));
			}
			if (!graph.containsKey(b)) {
				List<Node> temp = new LinkedList<Node>();
				temp.add(new Node(b, a, d));
				graph.put(b, temp);
			} else {
				graph.get(b).add(new Node(b, a, d));
			}
		}

		for (int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();

			BFS(a, b, graph, N);
		}
	}

	public static void BFS(int start, int end, HashMap<Integer, List<Node>> graph, int N) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(new int[] { start, 0 });
		boolean[] v = new boolean[N + 1];
		v[start] = true;
		while (!q.isEmpty()) {
			int[] now = q.poll();
			if (now[0] == end) {
				System.out.println(now[1]);
				return;
			}
			for (Node node : graph.get(now[0])) {
				if (v[node.to])
					continue;
				v[node.to] = true;
				q.add(new int[] { node.to, now[1] + node.dist });
			}
		}
	}

	static class Node {
		int from;
		int to;
		int dist;

		public Node(int from, int to, int dist) {
			super();
			this.from = from;
			this.to = to;
			this.dist = dist;
		}

		@Override
		public String toString() {
			return "Node [from=" + from + ", to=" + to + ", dist=" + dist + "]";
		}
	}
}