[BOJ1967] 트리의 지름(dfs, 인접 리스트)

 

 

---

문제링크

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

1967번: 트리의 지름

 

문제풀이

- 인접 리스트 사용해서 DFS 탐색 2번 수행

- 시간 복잡도 : O(V + E) 

 

절차

1) 1번 루트 노드에서 가장 비용이 큰 리프(leaf)노드를 찾음  (= 지름에 해당하는 한점)

2) 찾은 리프 노드를 시작점으로 dfs 탐색을 한번 더 수행하여 구한 최대 cost가 트리의 지름이다 

 

참고. 동일 문제 

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

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

 

제출코드

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

public class Main {
    
    static int N;

    static List<Edge>[] adj;
    static boolean[] visit;

    static int MAX = 0;
    static int LEAF;

    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 = 0; i <= N; i++) adj[i] = new ArrayList<>(); // 0번노드 초기화 안하니 NPE발생

        for(int i = 1; i <= N - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

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

    }

    static void dfs(int idx, int cost) {
        visit[idx] = true;
        if(MAX < cost) {
            MAX = cost;
            LEAF = idx;
        }

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

    static void pro() {
        visit = new boolean[N + 1];
        dfs(1, 0);

        Arrays.fill(visit, false);
        dfs(LEAF, 0);

        System.out.println(MAX);
    }

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