[BOJ 1240] 노드 사이의 거리 (Java, DFS)

 

 

---

문제 링크 

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

1240번: 노드사이의 거리

---

풀이 

- 인접 리스트로 풀 경우 노드와 연결된 간선 정보만 조회

- 시간 복잡도 : O(V + E), 그리고 M번 반복

- Node 클래스 정의 후 양방향 그래프 표현 

 

예제 입력에 따라 거리 값을 구하면 아래와 같다

# 시작, 끝 = 1, 2
[0, 0, 2, 5, 3]

# 시작, 끝 = 3, 2
[0, 5, 7, 0, 2]

---

제출 코드

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

public class Main {
    
     static StringBuilder sb = new StringBuilder();

    static int N, M;

    static int[] DIST;
    static List<Node>[] adj;

    static class Node {
        int number;
        int dist;

        public Node(int number, int dist) {
            this.number = number;
            this.dist = dist;
        }
    }
    
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        DIST = new int[N + 1];
        
        adj = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++) adj[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 dist = Integer.parseInt(st.nextToken());

            adj[from].add(new Node(to, dist));
            adj[to].add(new Node(from, dist));
        }

        while(M > 0) {
            M -= 1;
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());

            pro(start, end);
        }
    }

    static void dfs(int x, int _dist) {
        DIST[x] = _dist;

        for(Node n : adj[x]) {
            if(DIST[n.number] != -1) continue;

            DIST[n.number] = DIST[x] + n.dist;
            dfs(n.number, DIST[n.number]);
        }
    }

    static void pro(int start, int end) {
        Arrays.fill(DIST, -1);

        dfs(start, 0);

        sb.append(DIST[end]).append("\n");
    }

    public static void main(String[] args) throws Exception {
        input();
        System.out.println(sb);
    }
}