프로그래머스 - 가장 먼 노드 - 다익스트라 - Java

1. 문제

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

2. 풀이

1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

위 문제는 BFS로도 풀 수 있지만 최단거리 라는 점을 참고하여 나는 최단거리 알고리즘 다익스트라 로 풀었다.

✨핵심 Point

배열에서 같은 max값을 count하고싶은 경우

		int answer = 0;
        int max = 0;
        for(int dValue : d){
            if(max < dValue && dValue != (int) 1e9){
                max = dValue;
                answer = 1;
            } else if(max == dValue){
                answer++;
            }
        }
        return answer;

3. 전체 코드

import java.util.*;

class Solution {
    public int solution(int n, int[][] edge) {
        
        ArrayList<ArrayList<Node>> list = new ArrayList<>();
        int[] d = new int[edge.length+1];
        
        for(int i = 0; i <= edge.length; i++){
            list.add(new ArrayList<Node>());
            d[i] = (int)1e9;
        }
        
        for(int i = 0; i < edge.length; i++){
            int a = edge[i][0];
            int b = edge[i][1];
            
            list.get(a).add(new Node(b, 1));
            list.get(b).add(new Node(a, 1));
        }
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1, 0));
        d[1] = 0;
        
        while(!pq.isEmpty()){
            Node node = pq.poll();
            if(d[node.num] < node.cost) continue;
            
            for(Node getNode : list.get(node.num)){
                int costs = node.cost + getNode.cost;
                if(costs < d[getNode.num]){
                    d[getNode.num] = costs;
                    pq.add(new Node(getNode.num, costs));
                }
            }
        }
        int answer = 0;
        int max = 0;
        for(int dValue : d){
            if(max < dValue && dValue != (int) 1e9){
                max = dValue;
                answer = 1;
            } else if(max == dValue){
                answer++;
            }
        }
        return answer;
    }
    
    public class Node implements Comparable<Node> {
        int num;
        int cost;
        
        public Node(int num, int cost){
            this.num = num;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Node other){
            return Integer.compare(this.cost, other.cost);
        }
    }
}