백준 1240 - 노드사이의 거리

문제

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

리뷰

최단 경로 관련 알고리즘을 알고 있다면 쉽게 풀이할 수 있다고 생각되는 문제다.
단순히 트리를 그래프로 표현하고 주어진 두 정점 사이의 거리를 계산하는 문제였다.

bfs 로직을 이용하여 풀이했고, 시간복잡도는 $O(V+E)$의 형태인데 문제에서
주어지는 그래프들은 무조건 트리의 형태이므로 $O(N^2)$으로 수렴한다.
최악의 경우에도 연산 횟수가 1,000만 정도이므로 주어진 2초의 시간 제한을
무난히 통과한다.

코드

import java.util.*;

import static java.lang.Integer.parseInt;


public class Main {
    static boolean[] visited;
    static List<List<Node>> graph = new ArrayList<>();


    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringTokenizer st = new StringTokenizer(in.nextLine());
        int N = parseInt(st.nextToken());
        int M = parseInt(st.nextToken());

        visited = new boolean[N + 1];
        for (int i = 0; i <= N; i++)
            graph.add(new ArrayList<>());

        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(in.nextLine());
            int u = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());
            int w = parseInt(st.nextToken());

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

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(in.nextLine());
            int u = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());

            int result = bfs(u, v);
            sb.append(result + "\n");
        }

        System.out.println(sb);
        in.close();
    }

    static int bfs(int start, int end) {
        Queue<Node> queue = new ArrayDeque<>();
        Arrays.fill(visited, false);
        visited[start] = true;
        queue.offer(new Node(start, 0));

        while (!queue.isEmpty()) {
            Node current = queue.poll();
            if (current.vertex == end)
                return current.weight;

            for (Node next : graph.get(current.vertex)) {
                if (!visited[next.vertex]) {
                    visited[next.vertex] = true;
                    queue.offer(new Node(next.vertex, current.weight + next.weight));
                }
            }
        }

        return -1;
    }

    static class Node {
        int vertex, weight;

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

결과