프로그래머스 - 가장 먼 노드(Java)

다익스트라 문제입니다.

 

노드가 주어지고, 노드의 연결 정보가 간선으로 주어집니다.

가중치가 1인 그래프에서 노드 1을 기점으로 가장 먼 노드의 개수를 구하는 문제입니다.

 

시점이 주어지기 때문에, 다익스트라를 사용해야 하는 것을 알 수 있습니다.

 

[구현 코드]

import java.util.*;

class Solution {
    private static List<List<Integer>> graph;

    public static int solution(int n, int[][] edge) {
        int answer = 0;

        graph = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) graph.add(new ArrayList<>());

        for (int[] e : edge) {
            int a = e[0];
            int b = e[1];

            graph.get(a).add(b);
            graph.get(b).add(a);
        }

        int[] dis = dijkstra(n);

        int maxEdge = 0;
        for(int i=2; i<n+1; i++){
            if(dis[i] == 1_000_000_100) continue;
            maxEdge = Math.max(maxEdge, dis[i]);
        }

        for(int i=2; i<n+1; i++){
            if(dis[i] == maxEdge) answer++;
        }

        return answer;
    }

    private static int[] dijkstra(int n) {
        Queue<Integer> qu = new LinkedList<>();
        qu.add(1);
        boolean[] visited = new boolean[n + 1];
        int[] distance = new int[n+1];

        Arrays.fill(distance, 1_000_000_100);
        distance[1] = 0;
        while (!qu.isEmpty()) {
            Integer cn = qu.poll();

            if (visited[cn]) continue;
            visited[cn] = true;

            for (int i =0; i<graph.get(cn).size(); i++){
                int nn = graph.get(cn).get(i);

                if(distance[nn] > distance[cn] + 1){
                    distance[nn] = distance[cn] + 1;
                    qu.add(nn);
                }
            }
        }
        return distance;
    }
}