[프로그래머스] 가장 먼 노드 - JAVA

문제

https://school.programmers.co.kr/learn/courses/30/lessons/49189?language=java

프로그래머스

 

코드

import java.util.*;

class Solution {
    int dist [];
    List<Integer> graph [];
    public int solution(int n, int[][] edge) {
        graph = new ArrayList[n+1];
        
        for(int i=0;i<=n;i++){
            graph[i] = new ArrayList<>();
        }
        
        for(int i=0;i<edge.length;i++){
            graph[edge[i][0]].add(edge[i][1]);
            graph[edge[i][1]].add(edge[i][0]);
        }
        
        dist = new int [n+1];
        
        bfs();
        
        Arrays.sort(dist);
        int max = dist[n];
        
        int answer = 0;
        for(int i=0;i<=n;i++){
            if(max == dist[i]) answer+=1;
        }
        
        return answer;
    }
    
    public void bfs(){
        Queue<Integer> que = new LinkedList<>();
        Arrays.fill(dist, -1);
        
        que.add(1);
        dist[1] = 0;
        
        
        while(!que.isEmpty()){
            int cur = que.poll();
            
            for(int next : graph[cur]){
                if(dist[next] != - 1) continue;
                que.add(next);
                dist[next] = dist[cur] + 1;
            }
        }
        
    }
}