[백준 1167번 Java] 트리의 지름 - DFS

문제 난이도

GOLD II (문제 링크)

 

 

 

풀이

두 노드 간의 최장 경로인 트리의 지름을 구하는 문제이다.

 

모든 경우의 수를 구해서, 가장 큰 값을 찾아야하기 때문에 DFS에 적합하다. DFS 구현은 단순하니 이를 통해 문제를 쉽게 해결할 수 있다.

//dfs 호출부
int max = 0;
for (int i = 1; i <= V; i++) {
    boolean[] isVisit = new boolean[V + 1];
    max = Math.max(max, dfs(i, 0, isVisit));
}

//dfs 함수
 private static int dfs(int current, int dist, boolean[] isVisit) {
    isVisit[current] = true;
    int max = dist;

    for (Node node : tree.get(current)) {
        if (!isVisit[node.dest]) {
            max = Math.max(max, dfs(node.dest, dist + node.cost, isVisit));
        }
    }

    isVisit[current] = false;
    return max;
}

 

 

 

 

메모리 초과는 단순 이차원 배열을 통해 각 노드의 경우의 수를 계산했기 때문에 발생했다.

이는 리스트로 구현하여 해결하였다.

 

 

하지만, 모든 경우의 수를 구하면 시간 초과가 발생하는데, 모든 경우의 수를 구하게 되면 O(V^2)이 되며, 문제 조건에서 V가 100,000까지이기 때문에 최적화할 수 있는 방법이 필요하다.

 

임의의 노드 x에서 최장 경로 노드를 DFS를 통해 구했고, 이를 y라고 하자. 이 때 x의 최장 경로만을 구했기 때문에 시간 복잡도는 O(V)이다.

 

이제 x에서의 최장경로인 y에서의 최장경로를 다시 구해보자. 이 때 두 노드의 경로는 반드시 최장 경로가 될 수 밖에 없다. x을 기준으로 y를 찾아내면, y는 트리의 한쪽 끝에 위치하기 때문이다. 트리의 한쪽 끝에 위치한 y에서의 최장 경로가 지름이 될 수밖에 없다. 그리고 두번의 DFS만을 사용했기 때문에 여전히 O(V)이다.

 

이제 정리는 끝났으니, DFS 호출부와 구현부를 변경해보자.

//farthestNode : 임의의 노드(여기서는 1)에서의 가장 거리가 먼 노드
isVisit = new boolean[V + 1];
maxDistance = 0;
dfs(1, 0);

isVisit = new boolean[V + 1];
maxDistance = 0;
dfs(farthestNode, 0);


// dfs 함수
private static int dfs(int current, int dist, boolean[] isVisit) {
    isVisit[current] = true;
    int max = dist;

    for (Node node : tree.get(current)) {
        if (!isVisit[node.dest]) {
            max = Math.max(max, dfs(node.dest, dist + node.cost, isVisit));
        }
    }

    isVisit[current] = false;
    return max;
}

 

 

최적화를 통해, 단순 하나의 노드의 최장거리 계산을 DFS를 통해 단 두번만 호출하게 되어, O(V^2)이 O(V)가 되었다.

 

 

 

전체 코드

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

public class Main {

    static class Node {
        int dest;
        int cost;

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

    private static List<List<Node>> tree;
    private static int V;
    private static boolean[] isVisit;
    private static int maxDistance;
    private static int farthestNode;

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

        tree = new ArrayList<>();
        for (int i = 0; i <= V; i++) {
            tree.add(new ArrayList<>());
        }

        for (int i = 0; i < V; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());

            while (true) {
                int node = Integer.parseInt(st.nextToken());
                if (node == -1) break;
                int cost = Integer.parseInt(st.nextToken());
                tree.get(start).add(new Node(node, cost));
            }
        }

        isVisit = new boolean[V + 1];
        maxDistance = 0;
        dfs(1, 0);

        isVisit = new boolean[V + 1];
        maxDistance = 0;
        dfs(farthestNode, 0);

        System.out.println(maxDistance);
    }

    private static void dfs(int current, int dist) {
        isVisit[current] = true;

        if (dist > maxDistance) {
            maxDistance = dist;
            farthestNode = current;
        }

        for (Node node : tree.get(current)) {
            if (!isVisit[node.dest]) {
                dfs(node.dest, dist + node.cost);
            }
        }
    }
}