[백준] 1167 : 트리의 지름 (JAVA/자바)

문제

BOJ 1167 : 트리의 지름 - https://www.acmicpc.net/problem/1167

풀이

우선 입력으로 주어지는 연결관계를 그래프 형태로 나타낸 뒤 가장 긴 거리를 가지는 두 노드를 찾으면 된다.

도착 노드와 거리를 저장할 수 있도록 Edge class를 만들고, 각각 노드 별 ArrayList<Edge>를 만들어 인접 리스트를 구현해주었다. 예를 들어, 1번 노드와 연결되어 있는 노드들이 nodes[1].add(new Node(idx, weight)) 와 같은 식으로 들어간다.

처음에는 bfs로 모든 노드를 시작점으로 bfs를 n번 돌리도록 풀이했는데 시간초과가 났다.. 그래서 찾아보니, 가장 긴 지름을 만드는 노드 node1과 node2가 있다고 가정한다면, 임의의 노드 1개에서 가장 먼 노드는 node1이나 node2이다. 여기서 가장 긴 지름에 참여하는 노드 1개를 구하고 나머지 하나의 노드를 구하면 node1과 node2를 둘 다 구할 수 있다!

코드

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

public class Main {

    static int n;
    static int result = 0;
    static int max_node = 0;
    static ArrayList<Edge>[] nodes;

    static class Edge{ // 트리(그래프) 저장용
        int end;
        int weight;

        public Edge(int end, int weight) {
            this.end = end;
            this.weight = weight;
        }
    }

    static class Node{ // BFS 탐색용
        int idx;
        int cnt;

        public Node(int idx, int cnt) {
            this.idx = idx;
            this.cnt = cnt;
        }
    }

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

        nodes = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            nodes[i] = new ArrayList<>();
        }

        for (int i = 1; i <= n; i++) {
            String[] inputs = br.readLine().split(" ");
            int idx = Integer.parseInt(inputs[0]);
            int j = 1;
            while(true){
                int v_num = Integer.parseInt(inputs[j]);
                if(v_num == -1) break;
                int weight = Integer.parseInt(inputs[j+1]);

                nodes[idx].add(new Edge(v_num, weight));

                j += 2;
            }
        }

        bfs(1); // 임의의 노드 1
        bfs(max_node); // 임의의 노드 1에서 가장 먼 노드부터 bfs 시작

        System.out.println(result);

    }


    public static void bfs(int start) {

        boolean[] visited = new boolean[n + 1];

        Queue<Node> q = new LinkedList<>();
        q.add(new Node(start, 0));
        visited[start] = true;

        int max_cnt = 0;

        while (!q.isEmpty()) {
            Node now = q.poll();

            if(now.cnt>max_cnt){
                max_cnt = now.cnt;	// 가장 멀리 떨어진 노드의 거리
                max_node = now.idx;	// 가장 멀리 떨어진 노드의 번호
            }

            for (Edge e : nodes[now.idx]) {
                if(!visited[e.end]){
                    visited[e.end] = true;
                    q.add(new Node(e.end, now.cnt + e.weight));

                }
            }

        }

        result = Math.max(result, max_cnt);

    }
}

정리

✔ 알고리즘 분류 - 그래프 이론, 그래프 탐색, 트리, 깊이 우선 탐색
✔ 난이도 - 🟡 Gold 3

🤦‍♀️ 오늘의 메모

• 가장 먼 거리를 이루는 두개의 노드를 찾을 때 굳이 모든 점에서 탐색하지 않아도 된다. 임의의 점에서 시작하여 가장 먼 거리를 가지는 노드를 찾고, 그 노드에서 다시 한번 가장 먼 거리를 가지는 노드를 찾게 되면 총 2번의 탐색으로 트리의 지름을 구할 수 있다. 아직 잘 이해가 되지는 않지만 기억해둬야겠다.

참고 사이트

https://jellyinghead.tistory.com/88