[백준 Gold 2] 14657 준오는 최종인재야!! - Java

문제링크 : https://www.acmicpc.net/problem/14657

14657번: 준오는 최종인재야!!

 

접근 과정 : 

• 먼저 가장 많은 문제를 푸는 경우(트리의 지름)을 찾아야 한다.!!
•  + 가장 많은 문제를 푸는 경우가 여러개 존재한다면, 가장 시간이 짧은 것을 찾아야 한다.!!
• 즉, 가장 긴 트리의 지름 중에서 가장 가중치가 적은 경우를 찾고
• 이를 기준으로 다시 한번 조회해서, 정확한 가중치를 찾아서 반환한다!! 

 

소스 코드 및 결과 :

package BOJ;

/* 
    준오는 최종인재야!!

*/

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

public class BOJ14657 {

    static int N, T;
    static List<List<int[]>> links;
    static boolean[] solved;
    static int cnt, day, root;

    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());
        T = Integer.parseInt(st.nextToken());

        links = new ArrayList<>();
        links.add(new ArrayList<>());
        for (int i = 1; i <= N; i++) {
            links.add(new ArrayList<>());
        }
        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            links.get(a).add(new int[] { b, c });
            links.get(b).add(new int[] { a, c });
        }

        cnt = 1;
        root = 0;
        day = 0;

        solved = new boolean[N + 1];
        dfs(1, 1, 0);

        Arrays.fill(solved, false);

        dfs(root, 1, 0);

        day = day % T == 0 ? day / T : day / T + 1;
        System.out.println(day);

    }

    static void dfs(int now, int c, int t) {

        if (cnt < c) {
            root = now;
            cnt = c;
            day = t;
        } 
        else if (cnt == c && day > t) {
            root = now;
            day = t;

        }

        solved[now] = true;

        for (int[] next : links.get(now)) {
            if (!solved[next[0]]) {
                dfs(next[0], c + 1, t + next[1]);
            }
        }

    }
}