문제 풀이(40)

import java.util.*;
import java.io.*;

class Node implements Comparable<Node>{
    int vertex, value;
    
    Node(int vertex, int value)
    {
        this.vertex = vertex;
        this.value = value;
    }
    
    @Override
    public int compareTo(Node now)
    {
        return this.value - now.value;
    }
}

class Solution {
    
    static PriorityQueue<Node>pq = new PriorityQueue<>();
    static int[] dist;
    static boolean[] visited;
    static ArrayList<Node>[] adj ;
    
    public int solution(int n, int[][] edge) {
        int answer = 0;
        
        visited = new boolean[n + 1];
        
        adj = new ArrayList[n + 1];
        
        for(int i = 0; i <= n ;i++)
        {
            adj[i] = new ArrayList<>();
        }
        
        dist = new int[n + 1];
        
        for(int i=0 ;i <= n ;i++)
        {
            dist[i] = Integer.MAX_VALUE;
        }
        
        for(int[] e : edge)
        {
            int u = e[0];
            int v = e[1];
            
            adj[u].add(new Node(v,1));
            adj[v].add(new Node(u,1));
        }
        
        pq.offer(new Node(1,0));
        dist[1] = 0;
        
        while(!pq.isEmpty())
        {
            Node current = pq.poll();
            int c_v = current.vertex;
            if(visited[c_v])continue;
            visited[c_v] = true;
            
            for(int i = 0; i < adj[c_v].size(); i++)
            {
                Node tmp = adj[c_v].get(i);
                int next = tmp.vertex;
                int value = tmp.value;
                if(dist[next] > dist[c_v] + value)
                {
                    dist[next] = dist[c_v] + value;
                    pq.offer(new Node(next , dist[next] ));
                }
            }
        }
        
        Arrays.sort(dist, 1 ,n + 1);
        
        
        
        int max = dist[n];
        
        for(int i = 1; i <= n ;i++)
        {
            if(dist[i] == max)
            {

                answer++;
            }
        }
        
        return answer;
    }
}

Node 클래스는 그래프의 노드를 나타내는 클래스이다. 이 노드는 vertex (노드의 번호)와 value (노드까지의 거리)를 가지고 있다.
Comparable 인터페이스를 구현하고, compareTo 메서드를 오버라이드하여 노드들을 우선순위 큐에서 거리에 따라 정렬할 수 있도록 한다.

visited 배열은 방문한 노드를 추적하기 위한 배열로, n + 1 길이로 초기화된다.
adj는 각 노드에서 연결된 노드의 리스트를 나타내는 배열의 배열이다. 초기화할 때 각 노드별로 빈 ArrayList를 할당한다.
dist 배열은 시작 노드로부터의 거리를 저장하기 위한 배열로, 무한대 값으로 초기화된다.

edge 배열에 있는 간선 정보를 사용하여 adj 배열을 초기화한다. 양방향 간선으로 노드를 연결하며, 거리는 항상 1로 설정된다.

시작 노드(1번 노드)에서 출발하여 다른 노드까지의 최단 경로를 찾는 Dijkstra's 알고리즘을 구현한다.
시작 노드를 우선순위 큐에 넣고, 시작 노드로부터의 거리를 0으로 초기화한다.
우선순위 큐에서 노드를 하나씩 꺼내면서 최단 경로를 업데이트하고, 다음 노드를 큐에 넣는다.
visited 배열을 사용하여 이미 방문한 노드는 스킵한다.

Dijkstra's 알고리즘을 통해 모든 노드로부터 시작 노드로의 최단 거리를 계산한다.
그 중에서 최대 거리를 찾아 max 변수에 저장한다.

dist 배열을 1부터 n까지 정렬한다.
최장 거리 max와 같은 거리를 가지는 노드의 갯수를 answer 변수에 더해 최장 경로의 갯수를 계산한다.
answer를 반환하여 최장 경로의 갯수를 출력한다.