[BOJ] 1240 - 노드사이의 거리

문제 링크

1240-노드사이의 거리

문제 설명

입력

• 노드의 갯수 N
• 거리를 알고싶은 쌍의 갯수 M
• N-1 개의 줄에 각각 트리상에 연결된 두 점과 거리
• M 개의 쌍

출력

• M개의 줄에 입력받은 두 노드 사이의 거리

문제 풀이

Scanner 는 시간을 너무 잡아먹어서 Buffer 사용해서 풀어보는 연습해 봄
그냥 보자마자 그래프 탐색 생각할 수 있었음!

DFS (깊이 우선 탐색) 이용

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

public class Main {

    static ArrayList<Node> trees[];
    static int n;
    static int result = 0;

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

        n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        trees = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            trees[i] = new ArrayList<>();
        }

        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int distance = Integer.parseInt(st.nextToken());

            trees[start].add(new Node(end, distance));
            trees[end].add(new Node(start, distance));
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end =  Integer.parseInt(st.nextToken());
            dfs(start, end, -1, 0);
            sb.append(result + "\n");

        }
        System.out.println(sb);
    }

    public static void dfs(int start, int end, int prev, int distance) {
        if (start == end) result = distance;

        for (Node nextNode : trees[end]) {
            if (nextNode.next != prev) {
                dfs(start, nextNode.next, end, distance + nextNode.dis);
            }
        }
    }

    static class Node {
        int next;
        int dis;

        Node(int next, int dis) {
            this.next = next;
            this.dis = dis;
        }
    }
}