[JAVA] 백준 1967 트리의지름_트리

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

문제 : 

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

 

 

접근 : 

 

  - root 노드에서부터 리프노드까지 탐색을 진행하여 가장 긴 길이의 리프 노드를 찾는다.

 

  - 찾은 리프 노드에서 부터 가장 먼 노드까지 길이를 계산한 후 결과를 출력한다.

 

 

 

코드 구현 : 

 

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

public class Main {
    private static Map<Integer,List<Node>> graph;
    private static Node end;

    static class Node{
        int idx;
        int weight;

        public Node(int idx, int weight){
            this.idx = idx;
            this.weight = weight;
        }

        public int getIdx() {
            return this.idx;
        }
        public int getWeight() {
            return this.weight;
        }
    }

    private static void dfs(int before, int now, int temp_sum) {
        if(graph.get(now).size() == 1 && graph.get(now).get(0).getIdx() == before) {
            if(temp_sum > end.getWeight()) end = new Node(now, temp_sum);
            return;
        }

        for(Node next : graph.get(now)){
            if(next.getIdx() == before) continue;
            dfs(now, next.getIdx(), temp_sum + next.getWeight());
        }
    }

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

        int n = Integer.parseInt(br.readLine());

        if(n == 1){
            System.out.println(0);
            return;
        }
        graph = new HashMap<>();
        end = new Node(0,0);
        String[] inputs;
        int a, b, w;

        for(int i = 1 ; i < n ; i++){
            inputs = br.readLine().split(" ");
            a = Integer.parseInt(inputs[0]);
            b = Integer.parseInt(inputs[1]);
            w = Integer.parseInt(inputs[2]);
            if(graph.containsKey(a)){
                graph.get(a).add(new Node(b, w));
            }else{
                List<Node> temp = new ArrayList<>();
                temp.add(new Node(b, w));
                graph.put(a, temp);
            }
            if(graph.containsKey(b)){
                graph.get(b).add(new Node(a, w));
            }else{
                List<Node> temp = new ArrayList<>();
                temp.add(new Node(a, w));
                graph.put(b, temp);
            }
        }
        //1을 root로 가장 긴 노드 탐색
        dfs(1,1,0);

        // 가장 긴 노드에서 가장 먼거리 탐색
        int root = end.getIdx();
        Node child = graph.get(root).get(0);
        dfs(root, child.getIdx(), child.getWeight());

        System.out.print(end.getWeight());
        br.close();
    }
}

 

 

유사 문제 : 

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

 

* 입력 처리만 다르고 나머지 풀이법은 같음

 

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

public class Main {
    private static Map<Integer,List<Node>> graph;
    private static Node end;

    static class Node{
        int idx;
        int weight;

        public Node(int idx, int weight){
            this.idx = idx;
            this.weight = weight;
        }

        public int getIdx() {
            return this.idx;
        }
        public int getWeight() {
            return this.weight;
        }
    }

    private static void dfs(int before, int now, int temp_sum) {
        if(graph.get(now).size() == 1 && graph.get(now).get(0).getIdx() == before) {
            if(temp_sum > end.getWeight()) end = new Node(now, temp_sum);
            return;
        }

        for(Node next : graph.get(now)){
            if(next.getIdx() == before) continue;
            dfs(now, next.getIdx(), temp_sum + next.getWeight());
        }
    }

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

        int n = Integer.parseInt(br.readLine());
        graph = new HashMap<>();
        end = new Node(0,0);
        String[] inputs;
        int a;

        for(int i = 1 ; i <= n ; i++){
            inputs = br.readLine().split(" ");
            a = Integer.parseInt(inputs[0]);
            graph.put(a, new ArrayList<>());
            for(int j = 1 ; j < inputs.length-1 ; j+=2) {
                graph.get(a).add(new Node(Integer.parseInt(inputs[j]), Integer.parseInt(inputs[j + 1])));
            }
        }
        // 각 노드에서 대해서 가장 먼거리 탐색
        dfs(1, 1, 0);

        // 가장 긴 노드에서 가장 먼거리 탐색
        int root = end.getIdx();
        Node child = graph.get(root).get(0);
        dfs(root, child.getIdx(), child.getWeight());

        System.out.print(end.getWeight());
        br.close();
    }
}