문제

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

해설

1. 주어진 값으로 트리를 구성한다.

2. 임의 노드 선정

3. 임의 노드부터 길이가 가장 먼 노드를 찾는다.

4. 찾은 노드를 기준 노드로 선정한다.

5. 선정한 기준 노드로부터 가장 먼 길이에 있는 노드를 찾는다.

6. 두 노드 사이의 길이를 구하면 트리 지름이 된다.

메모

로직은 BFS 메서드에 임의 노드와 초기 길이 0을 파라미터로 넣고 로직을 실행한다. 임의 노드로 부터 엣지까지의 거리를 거리 배열(1차원)에 기록하면서 maxLen 값을 구한 후 마지막 maxLen가 구해진 Node를 다시 기준 노드로 선정한 후 방문 배열과 거리배열을 초기화 시킨 다음 BFS메서드에 기준 노드와 초기 거리값 0을 파라미터로 넣고 최종 maxLen를 출력한다.

코드

public class J1176_2 {
    static LinkedList<int[]>[] A;
    static boolean[] visited;
    static int node;
    static int[] distance;
    static int max = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        Scanner scanner = new Scanner(System.in);
        int num = scanner.nextInt();
        visited = new boolean[num+1];

        A = new LinkedList[num+1];
        for(int i = 1; i <= num; i++){
            A[i] = new LinkedList<>();
        }
        int cnt = 1;
        for(int i = 1; i <= num; i++){
            int n = scanner.nextInt();
            while(true) {
                int e = scanner.nextInt();
                if (e == -1) {
                    break;
                }
                int dis = scanner.nextInt();
                A[n].add(new int[] {e, dis});
            }
        }
        distance = new int[num+1];
        BFS(1, 0);
        visited = new boolean[num+1];
        distance = new int[num+1];
        BFS(node, distance[node]);
        System.out.println(max);
    }

    public static void BFS(int n, int dis){
        Queue<Integer> queue = new LinkedList<>();
        visited[n] = true;
        queue.add(n);
        distance[n] = dis;
        while(!queue.isEmpty()){
            int now = queue.poll();
            for(int[] i : A[now]){
                if(!visited[i[0]]){
                    visited[i[0]] = true;
                    distance[i[0]] = i[1]+distance[now];
                    if(distance[i[0]] > max){
                        max = distance[i[0]];
                        node = i[0];
                    }
                    queue.add(i[0]);
                }
            }
        }

    }
}