1240번: 노드사이의 거리

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

문제

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

입력

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

출력

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

예제 입력 1

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

예제 출력 1

2
7

+) 예제 입력 2

7 2
2 1 2
4 3 2
1 4 3
4 5 4
5 6 4
5 7 4
2 6
3 7

+) 예제 출력 2

13
10

풀이

package tree;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main_1240 {

    private static int numberOfNode;
    private static int numberOfTarget;
    private static int[][] distance;
    private static int[][] target;
    private static boolean[][] connect;

    public static void main(String[] args) throws IOException {
        input();
        process();
        output();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());

        numberOfNode = Integer.parseInt(st.nextToken());
        numberOfTarget = Integer.parseInt(st.nextToken());

        distance = new int[numberOfNode + 1][numberOfNode + 1];
        connect = new boolean[numberOfNode + 1][numberOfNode + 1];
        target = new int[numberOfTarget][2];

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

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            distance[a][b] = d;
            distance[b][a] = d;
            connect[a][b] = true;
            connect[b][a] = true;
        }

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

            target[i][0] = Integer.parseInt(st.nextToken());
            target[i][1] = Integer.parseInt(st.nextToken());
        }

    }

    private static void process() {
        for (int i = 0; i < numberOfTarget; i++) {
            int start = target[i][0];
            int destination = target[i][1];

            if (distance[start][destination] != 0) {
                continue;
            }

            if (distance[destination][start] != 0) {
                distance[start][destination] = distance[destination][start];
                return;
            }

            searchAllDistance(start);
        }
    }

    private static void searchAllDistance(int start) {
        List<Integer> connectNodes = getAdjacencyNodes(start);

        for (int connectNode : connectNodes) {
            List<Integer> nextNodes = getAdjacencyNodes(connectNode);

            for (int nextNode : nextNodes) {
                searchNextDistance(start, connectNode, nextNode);
            }
        }
    }

    private static void searchNextDistance(int start, int connectNode, int nextNode) {
        if (nextNode == start) {
            return;
        }

        distance[start][nextNode] = distance[start][connectNode] + distance[connectNode][nextNode];
        distance[nextNode][start] = distance[start][nextNode];

        List<Integer> nextAdjacencyNodes = getAdjacencyNodes(nextNode);

        for (int nextAdjacencyNode : nextAdjacencyNodes) {
            if (nextAdjacencyNode == connectNode) {
                continue;
            }

            searchNextDistance(start, nextNode, nextAdjacencyNode);
        }
    }

    private static List<Integer> getAdjacencyNodes(int node) {
        List<Integer> result = new ArrayList<>();

        for (int adjacencyNode = 1; adjacencyNode <= numberOfNode; adjacencyNode++) {
            if (connect[node][adjacencyNode]) {
                result.add(adjacencyNode);
            }
        }

        return result;
    }

    private static void output() {
        for (int i = 0; i < numberOfTarget; i++) {
            int start = target[i][0];
            int destination = target[i][1];

            System.out.println(distance[start][destination]);
        }
    }

}