[JAVA] 백준 1967번 【G4.트리의 지름】

문제

1967번: 트리의 지름

 

풀이

1️⃣ dfs를 이용한 풀이

💡 떠오른 Idea

처음에는 문제에서 친절하게 부모 노드를 명시해서 알려줘서 다른 방향으로 많이 생각했던 것 같다.

근데, 이 문제는 부모 노드를 특정해서 문제를 풀기보다는 모든 노드가 루트 노드가 될 수 있음을 가정해서 푸는 것이 편리하다.

예시에서 나온 그림은 위와 같은데 사실 위 그림은

9 를 최상단 노드라고 생각하고 그리면 위와 같이 그려질 수 있다.

그리고 9 → 5 → 3 → 6 → 12 노드 순으로 가면 예제의 답이 나온다는 사실을 알 수 있다.

즉, 모든 노드를 최상단 루트로 가정해보고

각 루트에서 dfs 로 깊이 탐색을 했을 때, 가중치를 최댓값으로 갱신하는 방법을 사용하면 최대 지름을 구할 수 있게 된다.

 

public class Main {
    static int sum = 0;
    static int ans = 0;
    static boolean[] checked;
    static Node[] nodes;

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

        checked = new boolean[N + 1];
        nodes = new Node[N + 1];

        for (int i = 0; i < N + 1; i++) {
            nodes[i] = new Node(i);
        }

        for (int i = 0; i < N - 1; i++) {
            String[] input = br.readLine().split(" ");
            int u = Integer.parseInt(input[0]);
            int v = Integer.parseInt(input[1]);
            int cost = Integer.parseInt(input[2]);

            Node U = new Node(u, cost);
            Node V = new Node(v, cost);

            nodes[u].connects.add(V);
            nodes[v].connects.add(U);

        }

        for (int i = 1; i <= N; i++) {
            Node root = nodes[i];
            checked[root.idx] = true;
            dfs(root);
            checked[root.idx] = false;
        }
        System.out.println(ans);

    }

    private static void dfs(Node node) {
        ans = Math.max(ans, sum);

        for (Node connect : node.connects) {
            if (!checked[connect.idx]) {
                sum += connect.cost;
                checked[connect.idx] = true;
                dfs(nodes[connect.idx]);
                sum -= connect.cost;
                checked[connect.idx] = false;
            }
        }

    }


    static class Node {
        int idx;
        List<Node> connects = new ArrayList<>();
        int cost;

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

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

 

결과

 

2️⃣ 트리의 특징을 이용한 풀이

💡

이 방법은 이 문제와 유사한 문제인

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

를 풀어보고 깨달은 방법이다.

가장 거리가 먼 두 노드, node1 과 node2 가 있다고 가정했을 때,

임의의 노드 x에서 출발해서 얻은 최대 비용의 경로의 최종 도착점은 node 1 혹은 node 2라는 것이다.

그리고 node 1 에서 출발한 최대 비용의 경로 최종 도착점은 node2가 된다.

예제 그림에서도, 특정 노드를 최상위 노드로 두고 경로를 구해보면 가장 긴 경로의 끝은 항상 9 혹은 12임을 알 수 있다.

이러한 특징을 이용해서, 임의의 노드 1번에서 출발하여 가장 큰 비용의 경로를 구하고, 그 경로 끝 노드 정보를 저장한 다음

경로 끝 노드 정보에서 가장 긴 경로를 찾으면, 그 경로가 트리에서 가장 큰 비용의 경로가 됨을 알 수 있다.

 

public class Main {
    static int sum = 0;
    static int ans = 0;
    static int maxIdx = 0;
    static boolean[] checked;
    static Node[] nodes;

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

        checked = new boolean[N + 1];
        nodes = new Node[N + 1];

        for (int i = 0; i < N + 1; i++) {
            nodes[i] = new Node(i);
        }

        for (int i = 0; i < N - 1; i++) {
            String[] input = br.readLine().split(" ");
            int u = Integer.parseInt(input[0]);
            int v = Integer.parseInt(input[1]);
            int cost = Integer.parseInt(input[2]);

            Node U = new Node(u, cost);
            Node V = new Node(v, cost);

            nodes[u].connects.add(V);
            nodes[v].connects.add(U);

        }

        dfs(1);
        dfs(maxIdx);

        System.out.println(ans);

    }

    private static void dfs(int i) {
        Node root = nodes[i];
        checked[root.idx] = true;
        dfs(root);
        checked[root.idx] = false;
    }

    private static void dfs(Node node) {
        if (ans < sum) {
            ans = sum;
            maxIdx = node.idx;
        }

        for (Node connect : node.connects) {
            if (!checked[connect.idx]) {
                sum += connect.cost;
                checked[connect.idx] = true;
                dfs(nodes[connect.idx]);
                sum -= connect.cost;
                checked[connect.idx] = false;
            }
        }

    }


    static class Node {
        int idx;
        List<Node> connects = new ArrayList<>();
        int cost;

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

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

결과

이전 방식은 모든 노드에서 탐색이 필요했지만, 두번째 풀이는 2번의 탐색만 수행하면 되기 때문에 실행속도가 비약적으로 개선됨을 알 수 있다.