[백준] 1967. 트리의 지름

문제

 

풀이

처음 시도했던 방법은 1번의 자식노드들을 시작점으로 잡아 DFS를 통해 탐색하면서 왼쪽 자식과의 거리, 오른쪽 자식과의 거리, 부모와의 거리 중에 상위 2개의 값을 골라 최대값을 갱신하는 방법으로 진행하였다. 그리고 그 최대값이 1번의 다른 줄기와 연결할 수 있는지(notCompleted), 아니면 이미 완성된 지름인지(completed) 판별하는 flag를 통해 최대 지름을 구하려고 했다.

이 방법이 잘못된 이유는 먼저 문제에서 이진 트리라는 조건이 없는데 이진트리라고 가정하고 풀었기 때문이고, 또한 위의 그래프에서 
4-7 : 100 / 4-8 : 100으로 수정한 경우 왼쪽 줄기의 최대값이 200이 나와야하는데 4의 부모노드인 2가 자식이 하나밖에 없기 때문에 200 + 5로 갱신되는 문제점이 존재한다.

틀린 풀이는 다음과 같다. (사실 풀면서도 일반화시키지 못한 조건이 너무 많아 잘못된 방법인 것 같았지만 논리상 문제를 찾지 못해서 그대로 진행했었다.)

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

public class Solution1967 {
    static class Node {
        int dest;
        int weight;

        public Node(int dest, int weight) {
            this.dest = dest;
            this.weight = weight;
        }
    }
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N, maxLength;
    static boolean isCompleted;
    static ArrayList<Node>[] nodes;
    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        nodes = new ArrayList[N+1];

        for (int i = 0; i < N-1; i++) {
            String[] line = br.readLine().split(" ");
            int idx = Integer.parseInt(line[0]);
            if (nodes[idx] == null)
                nodes[idx] = new ArrayList<>();
            nodes[idx].add(new Node(Integer.parseInt(line[1]), Integer.parseInt(line[2])));
        }

        if (N == 1) {
            System.out.println(0);
            return;
        }

        ArrayList<Integer> completed = new ArrayList<>();
        ArrayList<Integer> notCompleted = new ArrayList<>();
        for(Node n : nodes[1]) {
            isCompleted = false;
            int len = dfs(n.dest, n.weight);
            if (!isCompleted)
                notCompleted.add(len);
            else
                completed.add(len);
        }

        completed.sort(Integer::compareTo);
        notCompleted.sort(Integer::compareTo);

        System.out.println(completed);
        System.out.println(notCompleted);
        int maxCompleted = 0, maxNotCompleted = 0;
        if (completed.size() > 0)
            maxCompleted = completed.get(completed.size() - 1);
        if (notCompleted.size() > 0)
            maxNotCompleted = notCompleted.get(notCompleted.size() - 1);

        if (notCompleted.size() < 2)
            System.out.println(Math.max(maxCompleted, maxNotCompleted));
        else {
            int secondNotCompleted = notCompleted.get(notCompleted.size() - 2);
            System.out.println(Math.max(maxCompleted, maxNotCompleted + secondNotCompleted));
        }
    }

    private static int dfs(int idx, int len) {
        if (nodes[idx] == null)
            return len;

        int[] max = new int[2];
        for (Node n : nodes[idx]) {
            int curLen = dfs(n.dest, n.weight);
            if (max[1] == 0)
                max[1] = curLen;
            else if (max[0] < curLen)
                max[0] = curLen;
            else if (max[1] < curLen)
                max[1] = curLen;
        }
        if (max[0] > len && max[1] > len)
            isCompleted = true;
        else if (isCompleted )
            return max[0] + max[1];
    }
}

그래서 다음으로 생각했던 방법은 먼저 1번 노드에서 dfs를 진행해서 가장 먼 점(restartIdx)를 찾고 이 점에서 다시 가장 먼 점을 찾아 트리의 최대 지름을  구하는 방법이었다.

이 방법을 위해서는 문제에서 단방향이라고 말했지만 양방향으로 연관관계를 생성해야 하고 첫 번째로 생각했던 방법은 인접행렬을 통해 구하는 방법이었다. 하지만 인접 행렬의 경우 최대 10000 * 10000 개의 배열이 만들어지고 이로 인해 메모리 초과가 발생하였다.

두 번째로 선택한 방법은 인접 리스트를 통해 구하는 방법으로 src-dest : weight의 관계에 있다면 map[src]에 dest에 정보를, map[dest]에 src의 정보를 저장하는 방식으로 진행하였고 메모리 초과를 해결할 수 있었다.

최종 풀이는 다음과 같다.

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

public class Solution1967 {
    static class Node {
        int idx;
        int weight;

        public Node(int idx, int dist) {
            this.idx = idx;
            this.weight = dist;
        }
    }
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N, maxLength, restartIdx;
    static ArrayList<Node>[] nodes;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        N = Integer.parseInt(br.readLine());
        nodes = new ArrayList[N+1];
        for (int i = 0; i < N-1; i++) {
            String[] line = br.readLine().split(" ");
            int src = Integer.parseInt(line[0]);
            int dest = Integer.parseInt(line[1]);
            int weight =Integer.parseInt(line[2]);
            if (nodes[src] == null)
                nodes[src] = new ArrayList<>();
            if (nodes[dest] == null)
                nodes[dest] = new ArrayList<>();
            nodes[src].add(new Node(dest, weight));
            nodes[dest].add(new Node(src, weight));

        }

        if (N == 1) {
            System.out.println(0);
            return;
        }
        visited = new boolean[N+1];
        dfs(1, 0);

        maxLength = 0;
        visited = new boolean[N+1];
        dfs(restartIdx, 0);
        System.out.println(maxLength);
    }

    private static void dfs(int src, int weight) {
        if (visited[src]) return;
        visited[src] = true;

        if (maxLength < weight) {
            maxLength = weight;
            restartIdx = src;
        }

        for (int i = 0; i < nodes[src].size(); i++) {
            if (visited[nodes[src].get(i).idx]) continue;

            dfs(nodes[src].get(i).idx, weight + nodes[src].get(i).weight);
        }
    }
}