📙[Algo] 24.04.17 알고리즘

알고리즘 문제) BOJ 1240. 노드사이의 거리

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

문제 요약

• N개의 노드와 M개의 두 노드 쌍이 주어질 때, 두 노드 사이 거리 출력하기

시간 제한

• 2초

입력

• 노드 개수 N, 거리를 알고 싶은 노드 쌍의 개수 M
  • 2≤N≤1000
  • 1≤M≤1000
• N-1개줄에 두 점과 거리를 입력 받음
  • 거리는 1만 이하 자연수
• 마지막에 거리를 알고 싶은 M개의 노드 쌍이 한 쌍씩 입력 됨

출력

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

코드

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

public class Main {
    static int N, M;
    static ArrayList<Node>[] list;
    static int from, to, answer;

    static class Node{
        int no;
        int dist;

        Node(int no, int dist) {
            this.no = no;
            this.dist = dist;
        }
    }

    static void dfs(int cur, int prv, int total) {

        if (cur == to) {
            answer = total;
            return;
        }

        for (Node node : list[cur]) {
            if (node.no == prv) continue;

            dfs(node.no, cur, total + node.dist);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        list = new ArrayList[N + 1];
        for (int i = 0; i < N + 1; i++) {
            list[i] = new ArrayList<>();
        }

        int v1, v2, d;
        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            v1 = Integer.parseInt(st.nextToken());
            v2 = Integer.parseInt(st.nextToken());
            d = Integer.parseInt(st.nextToken());

            list[v1].add(new Node(v2, d));
            list[v2].add(new Node(v1, d));
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            from = Integer.parseInt(st.nextToken());
            to = Integer.parseInt(st.nextToken());

            answer = 0;
            dfs(from, 0, 0);
            sb.append(answer+"\\n");
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}