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

트리의 지름

풀이

문제의 자세한 내용은 링크를 참고하고 문제의 핵심은 하나의 노드에서 출발하여 다른 노드로 도착했을 때 가장 긴 경로를 찾는 것이다.

처음에는 그래서 모든 노드에서 다른 노드로 도착했을 때 값들 중 최대를 찾았으나 이렇게 풀게되면 dfs로 트리를 탐색하는데 재귀 호출을 많이 하기때문에 메모리 초과를 만난다.

그래서 단말 노드만 뽑아 dfs로 답을 구하려 했지만 마찬가지로 메모리초과를 만난다.

dfs를 하기때문에 경우의 수를 모두 탐색하려면 메모리초과를 겪는 것 같다.

그래서 생각을 다르게 하니 루트에서 가장 먼 노드를 구하고, 그 노드에서 가장 먼 노드까지의 경로가 트리의 지름일 수도 있겠다 싶었다.

그렇게 dfs를 총 2번하는 방법으로 코드를 작성하여 제출했고 답을 구했다.

추가

답을 다 제출하고 나서 생각을 해보니 전체 탐색을 하는 것은 문제가 안되었다. 대신 dfs가 아니라 bfs로 트리를 탐색했으면 재귀가 아니기때문에 메모리 초과를 겪지 않고 문제를 풀이할 수 있었을 것 같기도 하다.

코드

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

public class Main {
    static int[] dx = {-1, 0, 0, 1};
    static int[] dy = {0, -1, 1, 0};
    static int n, m;
    static Short[][] graph;
    static boolean[] visit;
    static int max = 0;
    static int maxIdx = 0;
    static ArrayList<Pair>[] tree;


    public static void main(String[] args) throws IOException {
        // write your code here
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        visit = new boolean[n + 1];
        tree = new ArrayList[n + 1];

        for (int i = 0; i <= n; i++) {
            tree[i] = new ArrayList<Pair>();
        }

        for (int i = 0; i < n - 1; i++) {
            String[] line = br.readLine().split(" ");
            short x = Short.parseShort(line[0]);
            short y = Short.parseShort(line[1]);
            short w = Short.parseShort(line[2]);
            tree[x].add(new Pair(y, w));
            tree[y].add(new Pair(x, w));

        }

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

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

        bw.write(max + "\n");
        bw.close();
        br.close();
    }

    private static void dfs(int start, int cost) {
        visit[start] = true;
        if(max < cost) {
            max = cost;
            maxIdx = start;
        }

        for (Pair child : tree[start]) {
            if (!visit[child.y]) {
                visit[child.y] = true;
                dfs(child.y, cost + child.weight);
            }
        }
    }

}

class Pair {
    public int y;
    public int weight;

    public Pair(int y, int weight) {
        this.y = y;
        this.weight = weight;
    }
}