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

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

프로그래머스

 

다익스트라 문제입니다.

 

기억해야할점

첫번째, 양방향 그래프로 표현해야 모든 노드를 방문할 수 있습니다.

단방향으로 할시 edge의 모양으로 인해 올바르게 그래프가 표현되지 않을 수 있습니다.

 

두번째, 문제 이해

처음에 n이 edge의 길이인줄알고 n만큼 반목문을 돌았다가 시간이 걸렸습니다.

 

 

 

import java.util.*;
class Solution {
    ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
    int[] d;
    public int solution(int n, int[][] edge) {
        int answer = 0;
        d = new int[n+1];
        Arrays.fill(d, Integer.MAX_VALUE);
        
        for(int i=0;i<=n;i++){
            graph.add(new ArrayList<Node>());
        }
        
        for(int i=0;i<edge.length;i++){
            int start = edge[i][0];
            int end = edge[i][1];
            graph.get(start).add(new Node(end, 1));
            graph.get(end).add(new Node(start, 1));
        }
        
        dijkstra();
        
        int max = 0;
        for(int i=1; i<=n; i++){
            if(max < d[i]){
                max = d[i];
            }
            System.out.print(" "+d[i]);
        }
        System.out.println("max:"+max);
        for(int i=1; i<=n ;i++){
            if(max == d[i]){
                answer+=1;
            }
        }
        return answer;
    }
    
    void dijkstra(){
        PriorityQueue<Node> pq = new PriorityQueue<Node>();
        pq.offer(new Node(1,0));
        d[1] = 0;
        
        while(!pq.isEmpty()){
            Node temp = pq.poll();
            int now = temp.index;
            int dist = temp.distance;
            
            if(d[now] < dist) continue;
            
            for(int i=0;i<graph.get(now).size();i++){
                int cost = d[now] + graph.get(now).get(i).distance;
                if(d[graph.get(now).get(i).index] > cost){
                    d[graph.get(now).get(i).index] = cost;
                    pq.offer(new Node(graph.get(now).get(i).index, cost));
                }
            }
        }
        
    }
    
    class Node implements Comparable<Node>{
        int index;
        int distance;
        Node(int index, int distance){
            this.index = index;
            this.distance = distance;
        }
        public int compareTo(Node other){
            if(this.distance > other.distance){
                return 1;
            }else{
                return -1;
            }
        }
    }
}