[Baekjoon] 백준 1240번: 노드 사이의 거리 (JAVA)

문제 1240번

1240번: 노드사이의 거리

[ 문제 풀이 ]

무향 그래프로 각 노드를 연결하는 ArrayList[]에 저장하고, 두 정점 사이의 거리를 구하는 문제입니다. Node 클래스를 정의하여 각 정점 값들과 거리를 저장합니다.

BFS 탐색을 활용하여 Queue에 다음 방문할 위치와 거리를 저장하고 탐색하며 거리를 계속 더해주면 됩니다. 무향 그래프이므로 visit[]을 사용하여 방문한 정점인지 체크해줍니다.

[ 코드 ]

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    private static class Node {
        int num, cost;
        public Node(int num, int cost) {
            this.num = num;
            this.cost = cost;
        }
    }

    private static ArrayList<Node>[] tree;
    private static int N;

    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 = new StringTokenizer(br.readLine());

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

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

        for (int i = 0; i < N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            tree[n1].add(new Node(n2, cost));
            tree[n2].add(new Node(n1, cost));
        }

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int n1 = Integer.parseInt(st.nextToken());
            int n2 = Integer.parseInt(st.nextToken());
            bw.write(String.valueOf(getDistance(n1, n2)));
            bw.newLine();
        }
        bw.flush();
    }

    private static int getDistance(int n1, int n2) {
        Queue<Node> queue = new LinkedList<>();
        queue.offer(new Node(n1, 0));

        boolean[] visit = new boolean[N+1];
        visit[n1] = true;

        int dist = 0;
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (cur.num == n2) {
                dist = cur.cost;
                break;
            }

            for (Node next: tree[cur.num]) {
                if (visit[next.num]) continue;
                visit[next.num] = true;
                queue.offer(new Node(next.num, next.cost + cur.cost));
            }
        }
        return dist;
    }
}