[pro] 프로그래머스 level3 49189 가장 먼 노드 (Java) - 다익스트라

[문제]

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

프로그래머스

 

[풀이]

다익스트라를 이용해서 풀었다.

 

[코드]

 

import java.util.*;

class Solution {
    List<List<Integer>> graph = new ArrayList<>();
    int[] dist;
    public int solution(int n, int[][] edge) {
        int answer = 0;
        //1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지
        //1번 노드로부터 -> 모든 노드에 대한 최단 거리를 구한 후, 가장 멀리 떨어진 노드 개수 세기.
        //다익스트라
        
        for(int i=0; i<=n; i++){
            graph.add(new ArrayList<>());
        }
        
        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]);
        }
        
        dist = new int[n+1];
        dijkstra(1, dist);
        
        //내림차순 정렬
        Integer[] d = Arrays.stream(dist).boxed().toArray(Integer[]::new);
        Arrays.sort(d, Collections.reverseOrder());
        int max = d[0]; 
        answer++;
        for(int i=1; i<dist.length; i++){
            if(max==d[i]){
                answer++;
            }
        }
        
        return answer;
    }
    
    public void dijkstra(int now, int[] dist){
        for(int i=1; i<dist.length; i++){
            dist[i] = Integer.MAX_VALUE;
        }
        
        dist[now] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(now);
        
        while(!q.isEmpty()){
            int n = q.poll();
            
            for(int i=0; i<graph.get(n).size(); i++){
                int next = graph.get(n).get(i);
                if(dist[n]+1 < dist[next]){
                    dist[next] = dist[n] + 1;
                    q.add(next);
                }
            }
        }
    }
    
}