백준 - 트리의 지름

문제 링크 ▶︎ 트리의 지름

문제 파악

트리가 주어지고 가중치의 합산이 가장 긴 지름을 구하면 되는데, 해당 지름은 당연히 리프노드들 간의 가중치의 합산으로 이루어진다.

이 그림에서 이해할 수 있듯이, 아무런 노드에서 출발해서 가장 먼 노드를 찾고나면 해당 노드가 끝점이 될거고, 그 끝점에서 가장 멀리 떨어진 또 다른 끝점을 찾으면 된다.
문제를 바로 이해하긴 어려웠지만 그림을 잘 참고하면 이해하기 수월해진다.

접근 방법

1. 우선 양방향으로 이동가능한 트리이므로 양방향으로 해시맵을 만들어주고, n이 1일때는 트리가 없어서 그냥 0을 리턴해주는 방법으로 코드를 작성했다.

2. 전역변수로 탐색 시작 node와 탐색하는 동안의 노드 이동 거리인 dist를 0으로 세팅해주고 방문 배열도 선언해준다. 그리고 1을 시작 노드로 잡고(아무 노드로 해도 무방함) bfs 탐색을 해준다. bfs를 통해 최장거리가 나오면 해당 노드를 저장한다.

3. 해당 노드에서부터 진짜 지름을 찾아야하기 때문에 해당 노드를 시작으로 하고, 방문 배열을 재선언해주고 다시 bfs 탐색을 통해서 전체 dist를 알아내면 된다.

코드 구현

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

public class Main {
    public static int node;
    public static int dist;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        Map<Integer, List<int[]>> tree = new HashMap<>();
        for (int i = 0; i < n; i++) {
            tree.put(i+1, new ArrayList<>());
        }
        for (int i = 0; i < n - 1; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            tree.get(a).add(new int[]{b, c});
            tree.get(b).add(new int[]{a, c});
        }
        if (n == 1) {
            System.out.println(0);
            return;
        }
        node = 0;
        dist = 0;
        boolean[] visited = new boolean[n+1];
        visited[1] = true;
        depth(1, tree, visited);
        dist = 0;
        visited = new boolean[n+1];
        visited[node] = true;
        depth(node, tree, visited);
        System.out.println(dist);
    }

    public static void depth (int start, Map<Integer, List<int[]>> tree, boolean[] visited) {
        Deque<int[]> q = new ArrayDeque<>();
        q.add(new int[]{start, 0});
        while (!q.isEmpty()) {
            int[] cur = q.remove();
            int now = cur[0];
            int cost = cur[1];
            if (dist < cost) {
                dist = cost;
                node = now;
            }
            for (int[] next : tree.get(now)) {
                int nnow = next[0];
                int ncost = cost + next[1];
                if (!visited[nnow]) {
                    visited[nnow] = true;
                    q.add(new int[] {nnow, ncost});
                }
            }
        }
    }
}

개선 사항

양 끝점을 찾아서 풀어야겠다는 생각은 했으나 문제에서 그림 설명을 해주지 않았으면 풀이 방법에 오류가 있었을 것 같다. 그리고 트리에 대해서 더 다양하게 생각하고 문제를 풀 수 있도록 연습이 되는 문제였다.