[JAVA][Baekjoon] 1167번 트리의 지름 🌟🌟

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

📌 접근 방식

1️⃣ 임의의 노드에서 가장 먼 노드 찾기

• 트리의 아무 노드에서 시작하여 BFS를 실행
• 이때 얻어지는 가장 먼 노드는 트리의 지름에 해당하는 두 노드 중 하나이다

2️⃣ 가장 먼 노드에서 다시 BFS 실행

• 1단계에서 찾은 가장 먼 노드에서 다시 BFS를 실행
• 이번 BFS에서 얻은 가장 먼 거리가 트리의 지름이다

[알고리즘] 너비 우선 탐색 : BFS(Breadth-First-Search)

 

✅ PASS CODE

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static boolean[] visited;
    static int[] distance;
    static ArrayList<Edge>[] A;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        A = new ArrayList[N+1];
        for(int i=1; i<=N; i++) {
            A[i] = new ArrayList<>();
        }
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            int S = Integer.parseInt(st.nextToken());
            while(true) {
                int E = Integer.parseInt(st.nextToken());
                if(E == -1) break;
                int V = Integer.parseInt(st.nextToken());
                A[S].add(new Edge(E, V));
            }
        }
        distance = new int[N+1];
        visited = new boolean[N+1];
        int max = 1;
        BFS(1);
        for(int i = 2; i<=N; i++) {
            if(distance[i] > distance[max]) {
                max = i;
            }
        }
        distance = new int[N+1];
        visited = new boolean[N+1];
        BFS(max);
        Arrays.sort(distance);
        System.out.println(distance[N]);
    }
    private static void BFS(int index) {
        Queue<Integer> q = new LinkedList<>();
        q.add(index);
        visited[index] = true;
        while(!q.isEmpty()) {
            int cur = q.poll();
            for(Edge i : A[cur]) {
                int e = i.e;
                int v = i.value;
                if(!visited[e]) {
                    visited[e] = true;
                    q.add(e);
                    distance[e] = distance[cur] + v;
                }
            }
        }
    }
}
class Edge {
    public int e;
    public int value;
    public Edge(int e, int value) {
        this.e = e;
        this.value = value;

    }
}

 

😊 느낀 점

트리 구조가 처음에는 매우 복잡해보였지만, BFS를 두 번만 사용하면 간단하게 해결할 수 있었다.

처음엔 간선 정보를 저장하고 BFS를 구현하는 게 까다로웠는데, 문제를 차근차근 풀어가며 이해할 수 있었다. 🔥