[BOJ1167] 트리의 지름 (트리)

 

 

---

문제 링크

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

1167번: 트리의 지름

 

문제 풀이

- 앞서 MST 문제 풀이하다가 '트리의 지름'에 대한 이론을 알게 되었고, 관련 문제 풀이함 

 

'트리의 지름'에 대한 강의 영상을 찾아보니 초보 알고리즘이란다 (하하하.. 심플하긴하다)

 

 

https://dev-ljw1126.tistory.com/369

[BOJ20010] 악덕 영주 혜유 (크루스칼, 프림, MST, 최소신장트리, 트리의 지름)

 

절차

총 DFS 두 번 실행한다 

1) 인접 리스트로 간선의 정보를 정의한다. 

 

2) 임의 노드 (시작 노드 1로 지정)에서 dfs 실행하여 최대 가중치를 가지는 leaf 노드를 구한다 

이때 구한 leaf 노드가 트리의 지름을 구성하는 노드 중 하나이다  

 

3) 데이터 초기화 후 2)에서 구한 leaf 노드 시작점으로 하여 한번 더 dfs 수행

 이때 구한 최대 가중치가 트리의 지름이 된다

 

 

제출 코드

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

public class Main {
    
    static int N;

    static int leaf, max; 
    
    static List<Edge>[] adj;

    static boolean[] visit;
    
    static class Edge {
        int idx;
        int cost;

        public Edge(int idx, int cost) {
            this.idx = idx;
            this.cost = cost;
        }
    }
    
    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine()); // 정점의 개수

        adj = new ArrayList[N + 1];
        for(int i = 1; i <= N; i++) adj[i] = new ArrayList<>();

        // 정점 / (연결 정점과 가중치).. / -1(끝)
        for(int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());

            int to;
            while((to = Integer.parseInt(st.nextToken())) != -1) {
                int cost = Integer.parseInt(st.nextToken());

                adj[from].add(new Edge(to, cost));
                adj[to].add(new Edge(from, cost));
            }
        }
    }

    static void dfs(int node, int dist) {
        visit[node] = true;
        if(max < dist) {
            max = dist;
            leaf = node;
        }

        for(Edge next : adj[node]) {
            if(!visit[next.idx]) dfs(next.idx, dist + next.cost);
        }
    }

    static void pro() {
        // 트리의 지름을 구성하는 leaf 노드를 구함
        visit = new boolean[N + 1];
        dfs(1, 0);
        
        // leaf 노드 시작으로 최대 가중치 구함 (= 트리의 지름)
        Arrays.fill(visit, false);
        dfs(leaf, 0);

        System.out.println(max);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
    
}