[알고리즘] Leetcode_743_Network_Delay_Time

Problem

Solve

• n 개의 노드와 times에는 간선의 정보가 담겨있고, k 노드에서 시작하는 간선의 정보를 탐색한다.
• 일단 n 과 times 로 그래프를 생성한다.
  • List<List<Node>> graph = new ArrayList<>() 로 전체적인 그래프를 형성한다. 리스트 graph 의 각각의 index 는 해당 노드가 연결되는 간선의 정보와 같다.
  • 클래스 Node 를 생성하여 목적지인 v와 가중치인 w 로 생성자를 생성하여 연결시켜준다.
• 출발 노드에서부터 각 노드 간의 거리는 최단거리를 구하는 그리드 알고리즘인 다익스트라 알고리즘을 활용한다. 다익스트라 알고리즘은 음의 가중치의 간선이 없는 경우 사용되며, 우선순위 큐를 사용하여 최단 거리를 관리한다.
  시간복잡도는 O(V^2) 또는 O(V + E log V) (V: 노드의 수, E: 간선의 수)이다. 최적화된 버전인 힙(Heap)을 이용한 다익스트라 알고리즘도 존재하여 시간 복잡도를 O(V + E log V)로 줄일 수 있다.

  1. 시작 노드에서부터 모든 노드까지의 최단 거리를 저장할 배열 dist 을 초기화한다. 시작 노드의 최단 거리는 0으로, 나머지 노드들의 최단 거리는 무한대로 초기화합니다.
  2. 시작 노드를 우선순위 큐에 넣고, 시작 노드의 최단 거리를 0으로 설정한다.우선순위 큐에서 노드를 하나씩 꺼내면서 해당 노드와 연결된 노드들의 최단 거리를 갱신한다. 시작 노드에서 현재 노드를 거쳐서 다른 노드로 가는 거리가 더 짧은 경우, 해당 노드의 최단 거리를 갱신하고, 우선순위 큐에 추가한다.
  3. 우선순위 큐에서 꺼낸 노드를 방문한 것으로 표시하고, 다음 노드를 꺼내서 3번 과정을 반복한다. 이때, 이미 처리된 노드는 더 이상 고려하지 않는다.
  4. 모든 노드들의 최단 거리가 갱신되면 알고리즘이 종료된다.

class Node{
   int v,w;
    public Node(int v, int w){
        this.v = v;
        this.w = w;
    }
}
class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        List<List<Node>> graph = new ArrayList<>();

        for(int i = 0 ; i <= n ; i++){
            graph.add(new ArrayList<>());
        }
        for(int i = 0; i < times.length ; i++){
            int u = times[i][0];
            int v = times[i][1];
            int w = times[i][2];
            graph.get(u).add(new Node(v,w));
        }

		// 최단 거리를 저장할 배열 초기화
        int[] dist = new int[n+1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>((a,b) -> a.w - b.w);
        pq.offer(new Node(k,0));

        while(!pq.isEmpty()){
            Node cur = pq.poll();
            int from = cur.v;
            int time = cur.w;

			// 현재 노드와 연결된 노드들의 최단 거리 갱신
            for(Node adj : graph.get(from)){
                int to = adj.v;
                int distance = adj.w;

                if(dist[to] > time + distance){
                    int newDistance = time + distance;
                    dist[to] = newDistance;
                    pq.offer(new Node(to, newDistance));
                }

            }
        }
        
		// 모든 노드에 도달하는데 걸리는 최단 시간 중 가장 오래 걸리는 시간 찾기
        int maximum = Integer.MIN_VALUE;
        for(int i = 1; i <= n ; i++){
            if(i == k) continue;
            if(dist[i] == Integer.MAX_VALUE){
                maximum = -1;
                break;
            }
            maximum = Math.max(maximum, dist[i]);
        }
        return maximum;
        
        
    }
}

이 문제에서는 모든 노드에 도달하는데 걸리는 최단 시간 중 가장 오래 걸리는 시간을 반환하는 것이다. 이것도 모르고 다익스트라 알고리즘을 사용하여 최단 거리를 찾는 것인 줄 알고 가장 짧은 거리를 반환했다가 실패가 떴었다. 그리고 만약 출발노드에서 다른 노드들까지 간선이 존재하지 않는다면 즉, 거리가 갱신되지 않아 무한대일 경우에는 -1을 반환한다.

⭐️ 생각해보기

우선순위 큐를 이용해 가중치를 기준으로 오름차순으로 정렬을 시켜주어 해당 노드에서 인접한 노드들 중 가중치가 작은 노드부터 차례로 방문할 수 있도록 하였다.

PriorityQueue<Node> pq = new PriorityQueue<>((a,b) -> a.w - b.w);

이를 미리 클래스 Node 를 구현할 때, 오버라이딩으로 compareTo 를 해주면 그래프를 생성해줄 때 정렬된 채로 메모리에 저장이 될 수 있다.

class Node implements Comparable<Node> {
    int v,w;
    
    public Node(int v, int w) {
       this.v = v;
       this.w = w;
    }
    
    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.w, other.w);
    }
}