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

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

1967번: 트리의 지름

 

 

 

단순히 모든 node에대해 dfs / bfs를 수행해도 통과할수있는 문제

 

 

1) - 단순 bfs + 브루트포스

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    public static int N;
    public static int ans;
    public static boolean[] visited;
    public static int maxweight = Integer.MIN_VALUE;
    public static ArrayList<Node>[] tree;
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        tree = new ArrayList[N + 1];

        for(int i = 0 ; i <= N ; i++){
            tree[i] = new ArrayList<>();
        }
        for(int i = 0 ; i < N - 1 ; i++) {
            StringTokenizer st =
                    new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            tree[parent].add (new Node(child, weight));
            tree[child].add(new Node(parent, weight));
        }
        for(int i = 1 ; i <= N ; i++) {
            visited = new boolean[N + 1];
            Arrays.fill(visited,false);
            visit(i, 0);
        }

        System.out.println(maxweight);
    }

    public static void visit(int curNode  , int sum){
        visited[curNode] = true;
        maxweight = Math.max(maxweight,sum);
        for(Node child : tree[curNode]){
            if(!visited[child.num]) {
                visit(child.num, sum + child.weight);
            }
        }


    }

}

class Node{
    int num;
    int weight;
    ArrayList<Node> childList = new ArrayList<>();

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

}

 

 

 

 

 

 

2) 수학적인 접근 

 

1. 루트노드(1번노드) 에서 가장 거리가 먼 노드(해당 노드는 무조건 리프노드일 수밖에없음)를 구한다.

2. 해당 노드에서 dfs를 수행해서 가장 큰 거리를 구한다.

 

 

모든노드 dfs수행 -> 2개의 노드만 dfs수행으로 실행시간이 1/10이 줄어든다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;


public class Main {

    public static int N;
    public static boolean[] visited;
    public static int maxweight = Integer.MIN_VALUE;
    public static int maxIndex;
    public static ArrayList<Node>[] tree;
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        tree = new ArrayList[N + 1];

        for(int i = 0 ; i <= N ; i++){
            tree[i] = new ArrayList<>();
        }
        for(int i = 0 ; i < N - 1 ; i++) {
            StringTokenizer st =
                    new StringTokenizer(br.readLine());
            int parent = Integer.parseInt(st.nextToken());
            int child = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            tree[parent].add (new Node(child, weight));
            tree[child].add(new Node(parent, weight));
        }

            visited = new boolean[N + 1];

            visit(1, 0);
            Arrays.fill(visited,false);
            visit(maxIndex,0);


        System.out.println(maxweight);
    }

    public static void visit(int curNode  , int sum){
        visited[curNode] = true;
        if(maxweight < sum){
            maxweight = sum;
            maxIndex = curNode;
        }
        for(Node child : tree[curNode]){
            if(!visited[child.num]) {
                visit(child.num, sum + child.weight);
            }
        }


    }

}

class Node{
    int num;
    int weight;
    ArrayList<Node> childList = new ArrayList<>();

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

    @Override
    public String toString(){
        return "현재 노드 :" + num + "weight : " + weight;
    }

}