[프로그래머스] 가장먼노드 - 자바(JAVA)

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

코딩테스트 연습 - 가장 먼 노드

문제 해석

1번부터 n번까지의 노드가 있는 그래프가 존재합니다.

양방향 그래프를 가지며 간선의 weight는 모두 1으로 볼 수 있습니다.

그리고 1부터 n번까지의 거리를 모두 측정한 뒤 가장 멀리 떨어진 노드가 몇 개인지 찾아야 합니다.

 

문제 풀이 전 설계

1번을 출발지로 가지며 n번까지의 거리를 모두 최단거리로 구해야 합니다.

바로 다익스트라 알고리즘이 떠올랐기 때문에 다익스트라로 해결해보고자 합니다.

 

다익스트라에 대해 모르신다면 다음글을 읽고오시면 좋을 것 같습니다

https://junuuu.tistory.com/208?category=987844 

다익스트라(Dijkstra) 알고리즘

 

코드

import java.util.*;

class Solution {
    
    static class Node{
        int index;
        int weight;

        public Node(int index, int weight) {
            this.index = index;
            this.weight = weight;
        }
    }
    
    public int solution(int n, int[][] edge) {
        List<ArrayList<Integer>> graphs = new ArrayList<>();

        for(int i=0; i<=n; i++){
            graphs.add(new ArrayList<>());
        }

        for(int[] e: edge){
            graphs.get(e[0]).add(e[1]);
            graphs.get(e[1]).add(e[0]);
        }
        //양방향 그래프 생성

        //다익스트라 시작
        int[] DP = new int[n+1];
        Arrays.fill(DP, 50000+1);

        PriorityQueue<Node> pq = new PriorityQueue<>((c1,c2) -> c1.weight - c2.weight);
        pq.add(new Node(1,0)); //1번노드에서부터 시작해서 다익스트라로 모든 거리 구하기

        while(!pq.isEmpty()){
            Node cur = pq.poll();

            ArrayList<Integer> nextCandidates = graphs.get(cur.index);
            for(Integer nextCandidate : nextCandidates){
                if(cur.weight + 1 < DP[nextCandidate]){
                    DP[nextCandidate] = cur.weight+1;
                    pq.add(new Node(nextCandidate,cur.weight+1));
                }
            }
        }
        //다익스트라 끝
        
        //정답 도출
        int findMax = Integer.MIN_VALUE;

        for(int i=2; i<=n; i++){
            findMax = Math.max(DP[i],findMax);
        }

        int result = 0;
        for(int i=2; i<=n; i++){
            if(DP[i] != findMax){
                continue;
            }
            result++;
        }
        return result;        
    }
}