[백준] 1967 트리의 지름

1. 문제

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

1967번: 트리의 지름

2. 접근방법

트리에서 끝에 두개 잡고 쭉 늘어뜨려서 젤 길이 긴 얘 찾기

dfs쓰면 쉽게 풀이 가능

 

일단 주의할 점이 예제에서 이진트리라서 이진트리라 헷갈릴 수 있지만 자식이 여러개 일 수 있는 일반 트리이다.

 

두개를 잡고 쭉 늘어 뜨린다는 말은 두 줄만 사용 가능하다는 소리

 

바텀 업의 느낌으로 풀면 되고

한 노드에서 해야할 일은

1. 내 자식들 중 가장 긴 두 자식을 선택하기 ( 재귀로 바닥에서 내 자식까지 가장 긴 거리를 구하러 보낸 뒤 )

2. 가장 긴 두 자식의 합이 가장 큰 값인지 비교하기

3. 가장 긴 첫 번째 자식만 return하기

 

이렇게 3가지 작업만 해주면 된다.

3. 자바 코드

package backjoon;

import java.awt.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class P1967트리의지름 {

    static HashMap<Integer, ArrayList<Point>> tree = new HashMap<>();
    static int max = 0;
    public static void main(String[] args) throws Exception {
        //자식들 중 큰거 2개 합해서 max 비교 후 자식 중 비싼 얘만 위로
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            ArrayList<Point> list = tree.getOrDefault(a,new ArrayList<>());
            tree.put(a,list);
            list.add(new Point(b,c));
        }
        dfs(1);
        System.out.println(max);
    }

    static int dfs(int num){
        ArrayList<Point> childs = tree.get(num);
        int childBest = 0;
        int childSecond = 0;
        for(Point child : childs){
            int value = dfs(child.x) + child.y;
            if(childBest < value) {
                childSecond = childBest;
                childBest = value;
            }
            else if(childSecond < value) childSecond = value;
        }
        max = Math.max(max,childBest + childSecond);
        return childBest;
    }

}

4. 마치며

처음에 이진트리인 줄 알고 틀렸는데 요런 것 좀 잘 체크하자

https://lovelyunsh.tistory.com/166

뭔가 풀어본 것 같아서 찾아보니 예전에 풀었던 문제

그 때나 지금이나 똑같이 풀었네..