카테고리 없음

18126_너구리구구 (틀림.....)

베리영young 2024. 4. 12. 13:48

사용 알고리즘: bfs

사용 언어: java

 

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Queue;
import java.util.Scanner;

public class Main_bj_18126_너구리구구 {
    static int n;
    static ArrayList<int[]>[] al ;
    static int maxLength;
    static boolean[] visited;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        al = new ArrayList[n];
        visited = new boolean[n];
        visited[0] = true;
        for (int i = 0; i < n; i++) {
            al[i] = new ArrayList<>();
        }
        for (int i = 0; i < n-1; i++) {
            int a = sc.nextInt()-1;
            int b = sc.nextInt()-1;
            int c = sc.nextInt();
            al[a].add(new int[] {b,c});
            al[b].add(new int[] {a,c});
        }
        ///

        bfs();
        System.out.println(maxLength);
    }

    private static void bfs() {
        Queue<int[]> q = new ArrayDeque();
        q.offer(new int[] {0,0}); //현재 방, 이동 거리

        while (!q.isEmpty()) {
            int[] p = q.poll();

            for (int[] nxt : al[p[0]]) {
                if(!visited[nxt[0]]) {
                    visited[nxt[0]] = true;
                    maxLength = Math.max(maxLength, p[1] + nxt[1]);
                    q.offer(new int[] {nxt[0], nxt[1]});
                }
            }
        }
    }
}