[Baekjoon] 1967번: 트리의 지름

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

1967번: 트리의 지름

문제 설명

가중치가 있는 트리에서 모든 경로 중 가장 길이가 긴 경로의 가중치 합을 출력하면 된다. 먼저 DFS로 가장 가중치 합이 가장 큰 마지막 노드를 찾아낸 다음 그 노드에서 다시 DFS 처리하여 가장 가중치 합이 큰 경로, 즉 트리의 지름을 구하면 된다.

풀이 방법 1. 리스트 활용 - 통과

package baekjoon.dfs_bfs;

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

public class BOJ1967 {

    static int N, maxNodeIdx, max = Integer.MIN_VALUE;
    static ArrayList<Node> tree[];
    static boolean[] isVisited;

    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<>();
        }

        for (int i = 0; i < N - 1; i++) {
            int[] nodeInfo =
                    Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int parent = nodeInfo[0];
            int child = nodeInfo[1];
            int weight = nodeInfo[2];

            tree[parent].add(new Node(child, weight));
            tree[child].add(new Node(parent, weight));
        }

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

        isVisited = new boolean[N + 1];
        isVisited[maxNodeIdx] = true;
        dfs(maxNodeIdx, 0);

        System.out.print(max);
    }

    private static void dfs(int idx, int sum) {
        if (max < sum) {
            max = sum;
            maxNodeIdx = idx;
        }

        for (Node next : tree[idx]) {
            if (!isVisited[next.node]) {
                isVisited[next.node] = true;
                dfs(next.node, sum + next.weight);
            }
        }
    }

    private static class Node {
        int node;
        int weight;

        public Node(int node, int weight) {
            this.node = node;
            this.weight = weight;
        }
    }
}

풀이 방법 2. 배열 활용 - 메모리 초과

package baekjoon.dfs_bfs;

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

public class BOJ1967 {

    static int N, maxNodeIdx, max = Integer.MIN_VALUE;
    static int[][] tree;
    static boolean[][] isVisited;

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

        N = Integer.parseInt(br.readLine());

        tree = new int[N + 1][N + 1];

        for (int i = 0; i < N - 1; i++ {
            int[] nodeInfo = 
                Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int parent = nodeInfo[0];
            int child = nodeInfo[1];
            int weight = nodeInfo[2];

            tree[parent][child] = weight;
            tree[child][parent] = weight;
        }

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

        isVisited[maxNodeIdx][1] = true;
        isVisited[1][maxNodeIdx] = true;
        dfs(maxNodeIdx, 0);

        System.out.print(max);
    }

    private static void dfs(int x, int sum) {
        if (max < sum) {
            max = sum;
            maxNodeIdx = x;
        }

        for (int y = 1; y <= N; y++) {
            if (!isVisited[x][y] && tree[x][y] > 0) {
                sum += tree[x][y];
                isVisited[x][y] = true;
                isVisited[y][x] = true;
                dfs(y, sum);
                sum -= tree[x][y];
                isVisited[x][y] = false;
                isVisited[y][x] = false;
            }
        }
    }
}