오늘 풀어볼 문제는 ⭐노드 사이의 거리 문제이다.

1. 문제요약

1. 노드 N개의 트리가 주어진다.
2. 거리를 알고 싶은 쌍의 개수 M개가 주어진다.

1.1 제한

$2≤N≤1\,000$  
$1≤M≤1\,000$ 

• 트리 상에 연결된 두 점과 거리는 1000 이하인 자연수이다.
• 트리 노드의 번호는 $1$부터 $N$까지 자연수이며, 두 노드가 같은 번호를 갖는 경우는 없다.

2. 접근

이 문제에서 중요한 키워드는 "트리" 이다.

트리가 의미하는 3가지

1. 간선 수 최대 N-1
2. 순환 사이클 없음
3. 두 노드 간 경로는 항상 유일함 -> dfs/bfs 탐색

난 트리라는 키워드를 안읽는 바람에, 흔한 완전그래프인줄 알았고 결국 잘못된 길을 갔었다.

2.1 시간복잡도

해당 문제의 시간복잡도는 간단하다.

O(M * (N+E)) = 약 200백만

3. 코드

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

class Info {
    int to;
    int dis;

    public Info(int to, int dis){
        this.to=to;
        this.dis=dis;
    }
}

public class Main {
    static int N,M;
    static List<Info>[] graph;
    static boolean []visited;
    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());
        M = Integer.parseInt(st.nextToken());

        graph = new List[N+1];
        visited = new boolean[N+1];
        for(int i=1; i<=N; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=0; i<N-1; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int dis = Integer.parseInt(st.nextToken());

            graph[from].add(new Info(to, dis));
            graph[to].add(new Info(from, dis));
        }

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            Arrays.fill(visited, false);
            System.out.println(findDfs(a,b,0));
        }

    }

    static int findDfs(int now, int arrival, int nowDis) {
        visited[now]=true;
        if(now==arrival) return nowDis;
        for(int i=0; i<graph[now].size(); i++) {
            Info next = graph[now].get(i);
            if(visited[next.to]) continue;
            int result = findDfs(next.to, arrival, next.dis+nowDis);
            if(result>0) return result;
        }
        return -1;
    }
}