[백준] 1167번 트리의 지름

문제 설명

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

문제 풀이

• 우선 문제를 풀기전에 트리에 성질에 대해 파악해야 한다.

  1. 트리의 경우 사이클을 구성하지 않는다 (DFS 사용시 이전 노드만 제거하면 방문체크 불필요)
  2. 특정 노드에서 최장거리 노드는 지름을 구성하는 두 노드 중 하나의 노드이다.

• 위 2번 특징으로 인해 임의의 정점에서 최장거리 노드를 구하고 해당 노드에서 다시 최장거리를 구하면 전체 트리의 지름을 구할 수 있다.

소스 코드 (JAVA)

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

public class Main {
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static int N;
    public static ArrayList<Info>[] map;
    public static int[] dp;
    public static int maxV, maxD = 0;

    public static class Info {
        int n, d;

        public Info(int n, int d) {
            this.n = n;
            this.d = d;
        }
    }

    //cur에서 부터 가장 먼 정점 구하기
    //사이클이 없으므로 한번씩만 방문하게됨
    public static void solve(int before, int cur, int total) {
        if (total > maxD) {
            maxV = cur;
            maxD = total;
        }

        for (int i = 0; i < map[cur].size(); i++) {
            Info t = map[cur].get(i);
            if (t.n == before) continue;
            solve(cur, t.n, total + t.d);
        }
    }

    public static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        map = new ArrayList[N + 1];
        dp = new int[N + 1];
        Arrays.fill(dp, -1);
        for (int i = 1; i <= N; i++)
            map[i] = new ArrayList<>();
        for (int i = 0; i < N; i++){
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int cur = Integer.parseInt(st.nextToken());
            while(true) {
                int n = Integer.parseInt(st.nextToken());
                if (n == -1) break;
                int d = Integer.parseInt(st.nextToken());
                map[cur].add(new Info(n, d));
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        solve(0, 1, 0);
        maxD = 0;
        solve(0,maxV, 0);
        bw.write(maxD + "\n");
        bw.flush();
        bw.close();
        bw.close();
    }
}