[백준] 1167 트리의 지름 - 자바

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

1167번: 트리의 지름

문제 풀이

트리의 지름을 구하는 문제로 그래프 탐색을 사용하여 해결할 수 있다. 필자는 재귀를 통한 dfs로 구현하였다.

 

이 문제에서 중요한 점은 어떤 노드부터 시작해야 가장 긴 길이 즉, 지름을 구할 수 있는지이다. 모든 노드를 탐색하여 최대치를 업데이트 할 수 있지만 2번의 dfs를 통해 높이를 구할 수 있다.

 

임의의 노드에서 시작해 그 노드가 갖는 최대 길이에 해당하는 노드를 A라고 했을 때 이 트리의 높이는 A에서 dfs를 통해 구한 길이이다.

말로하면 헷갈리니 간단하게 문제 예시를 통해 알아보자. 다음과 같은 트리가 있다.

이 트리는 한 눈에 봐도 1-3-4-5의 노드를 거쳐 총 지름이 11이 나와야 한다. 즉, 이 트리의 지름은 1또는 5에서 시작하여 지름을 구할 수 있을 것이다. 이제 임의의 노드를 선택하여 가장 긴 길이를 갖는 노드를 찾아보자.

 1, 3, 4 노드를 dfs를 수행할 경우 가장 긴 길이를 갖는 노드는 5
2, 5 노드를 dfs를 수행할 경우 가장 긴 길이를 갖는 노드는 1

즉, 2번의 dfs를 통해 트리의 높이를 구하는 과정을 살펴보았다.

 

 

코드

package 백준;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

class Node{
    int idx;
    int distance;

    public Node(int idx, int distance) {
        this.idx = idx;
        this.distance = distance;
    }
}

public class b1167 {
    static List<Node>[] tree;
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

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

            while (true) {
                int to = Integer.parseInt(st.nextToken());
                if (to == -1) break;

                int cost = Integer.parseInt(st.nextToken());
                tree[from].add(new Node(to, cost));
            }
        }
        visit = new boolean[N + 1];

        dfs(1,0 );
        visit = new boolean[N + 1];

        dfs(maxDistanceIdx, 0);

        System.out.println(maxDistance);
    }

    static boolean visit[];
    static int maxDistance = 0;
    static int maxDistanceIdx = 0;
    public static void dfs(int idx, int distance) {

        if(distance > maxDistance) {
            maxDistance = distance;
            maxDistanceIdx = idx;
        }
        visit[idx] = true;

        for(int i = 0; i < tree[idx].size(); i++) {
            Node adj = tree[idx].get(i);
            int adjIdx = adj.idx;
            if(visit[adjIdx] == false) {
                dfs(adjIdx, adj.distance + distance);
                visit[adjIdx] = true;
            }
        }

    }
}