https://school.programmers.co.kr/learn/courses/30/lessons/49189

문제 설명
n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

제한사항
노드의 개수 n은 2 이상 20,000 이하입니다.
간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.
입출력 예
n vertex return
6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3
입출력 예 설명
예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

코드

import java.util.*;
class Solution {
    public int solution(int n, int[][] edge) {
        int answer = 0;
        int[] distance = new int [n+1]; //1번 노드로 부터의 거리를 담음
        boolean[] visited = new boolean [n+1]; //방문 여부
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<Integer>()); //그래프 초기화(각각의 노드를 표현하는 리스트 추가)
        }
        
        for(int i=0; i<edge.length; i++){ //연결된 그래프 생성
            graph.get(edge[i][0]).add(edge[i][1]);
            graph.get(edge[i][1]).add(edge[i][0]);
        }
        
        Queue<Integer> que = new LinkedList<>(); //검사 대상
        que.add(1);
        visited[1] = true;
        
        while(!que.isEmpty()){
            int current = que.poll();
            for(int adj : graph.get(current)){
                if(!visited[adj]){
                    distance[adj] = distance[current] + 1 ; //현재 검사중인 노드와 연결되어있으니까 +1
                    visited[adj] = true;
                    que.add(adj);
                }
            }
        }
            int maxDistance = Arrays.stream(distance).max().getAsInt();
                for(int i=2; i<=n; i++){
                    if(distance[i] == maxDistance){
                        answer++;
                    }
                }
        
        return answer;
    }
}

BFS로 문제를 해결했다.
(그래프 문제를 풀 때는 ArrayList<ArrayList> graph = new ArrayList<>();
와 같이 그래프를 생성해주고,
for(int i=0; i<=n; i++){
graph.add(new ArrayList()); //그래프 초기화(각각의 노드를 표현하는 리스트 추가)
}
이렇게 추가해주어야한다.
이렇게 해주지 않으면, graph.get(edge[i][0]).add(edge[i][1]); 이 부분에서 오류가 발생한다.)

그래프를 만든 후에는, 1번 노드부터 이어지는 노드들을 확인하며
방문하지 않았고 이어져있는 노드는 distance에 현재의 distance+1을 저장해주었다.
(distance[i]는 1번노드와 i번째 노드의 거리를 의미한다.)