[Java/알고리즘] 백준 14657 | 준오는 최종인재야!!

0. 메모리 및 실행시간

1. 제출 코드

(1) DFS로 풀기

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

public class Main {

    static int N, T;
    static int[] result;
    static boolean[] visited;
    static List<int[]>[] adj;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 최대한 많은 문제를 풀어야 해!! -> dfs 깊이를 최대로 해야 함

        N = Integer.parseInt(st.nextToken()); // 문제 수
        T = Integer.parseInt(st.nextToken()); // 하루 풀이 시간

        visited = new boolean[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 time = Integer.parseInt(st.nextToken());

            adj[from].add(new int[] {to, time});
            adj[to].add(new int[] {from, time});

        }

        // 답을 찾아보자
        // depth가 최대일 때의 가중치의 합(tmp)를 구하자
        // depth가 같다면 가중치의 합이 작아야 함
        // 즉, 트리의 지름과 같은 길이를 가지는 경로 중 가중치의 합이 최소인 경우를 찾아야 함

        // 트리의 지름 구하기
        // 첫 번재 끝 점 찾기
        result = new int[3];
        Arrays.fill(visited, false);
        Arrays.fill(result, 0);
        visited[1] = true;
        dfs(1, 0, 0);
        int firstNode = result[0];

        // 다른 끝 점을 찾아 DFS
        Arrays.fill(visited, false);
        Arrays.fill(result, 0);
        visited[firstNode] = true;
        dfs(firstNode, 0, 0);
        int sumWeight = result[2];

        System.out.println((sumWeight+T-1) / T);
        br.close();
    }

    static void dfs(int node, int depth, int sum) {
        // result -> node, depth, sum of weight
        if (depth > result[1] || depth == result[1] && sum < result[2]) {
            result[0] = node;
            result[1] = depth;
            result[2] = sum;
        }

        for (int[] edge : adj[node]) {
            if (!visited[edge[0]]) {
                visited[edge[0]] = true;
                dfs(edge[0], depth+1, sum+edge[1]);
            }
        }
    }

}

(2) BFS로 풀기

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

public class Main {

    static int N, T;
    static boolean[] visited;
    static List<int[]>[] adj;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 최대한 많은 문제를 풀어야 해!! -> dfs 깊이를 최대로 해야 함

        N = Integer.parseInt(st.nextToken()); // 문제 수
        T = Integer.parseInt(st.nextToken()); // 하루 풀이 시간

        visited = new boolean[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 time = Integer.parseInt(st.nextToken());

            adj[from].add(new int[] {to, time});
            adj[to].add(new int[] {from, time});

        }

        // 답을 찾아보자
        // depth가 최대일 때의 가중치의 합(tmp)를 구하자
        // depth가 같다면 가중치의 합이 작아야 함
        // 즉, 트리의 지름과 같은 길이를 가지는 경로 중 가중치의 합이 최소인 경우를 찾아야 함
        
        // 트리의 지름 구하기
        int[] fromOne = bfs(1);
        int tmp = fromOne[0];
        
        int[] fromTmp = bfs(tmp);
        int maxDist = fromTmp[2];

        System.out.println((maxDist+T-1) / T);
        br.close();
    }
    
    static int[] bfs(int start) {
    	// 노드 번호, MAX DEPTH, 가중치의 합 반환
    	int[] ans = new int[] {0, 0, 0};
    	
    	Arrays.fill(visited, false);
    	Queue<int[]> q = new ArrayDeque<>();
    	q.add(new int[] {start, 0, 0}); // 노드 번호, depth, 가중치의 합
    	visited[start] = true;
    	
    	while (!q.isEmpty()) {
    		int[] cur = q.poll();
    		
    		if (cur[1] > ans[1] || (cur[1] == ans[1] && cur[2] < ans[2])) {
    			ans[0] = cur[0];
    			ans[1] = cur[1];
    			ans[2] = cur[2];
    		}
    		
    		for (int[] edge : adj[cur[0]]) {
    			if (!visited[edge[0]]) {
    				q.add(new int[] {edge[0], cur[1]+1, cur[2]+edge[1]});
    				visited[edge[0]] = true;
    			}
    		}
    	}
    	
    	return ans;
    }
}

2. 풀이과정 및 리뷰

• 문제 접근: DFS 또는 BFS로 트리의 지름들 중 가중치의 합이 가장 적을 걸 찾자
• 시간복잡도: $O(N)$
• 풀이과정
  • 문제의 핵심 → 트리의 지름들 중 가중치의 합이 가장 잡은 경우를 찾자!
  • DFS or BFS를 통해 임의의 노드 (여기서는 1)에서 가장 먼 노드를 고르자
  • 그 노드부터 다시 DFS or BFS를 진행하면서 depth와 가중치의 합 추적
  • depth가 가장 높은 경로에 대한 가중치 합 저장. 만약 depth가 같다면 가중치의 합이 적은 경우를 저장