soHyun

웹개발자로 성장하기

1 minute read

네트워크 딜레이 타임

https://leetcode.com/problems/network-delay-time/

문제 :

  • k에서 출발해 모든 노드가 신호를 받을 수 있는 시간을 계산하라.
  • 한 군데라도 노드에 도달할 수 없는 경우 -1 반환
  • 입력값 (u, v, w)는 각각 출발지, 도착지, 소요시간으로 구성되며, 전체 노드의 개수는 n개

예시 1

  • 입력: times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
  • 출력: 2

예시 2

  • 입력: times = [[1,2,1]], n = 2, k = 1
  • 출력: 1

예시 3

  • 입력: times = [[1,2,1]], n = 2, k = 2
  • 출력: -1

다익스트라 알고리즘

: 항상 노드 주변의 최단 경로만을 택하는 대표적인 그리디 알고리즘 중 하나
다익스트라 알고리즘 구현시 우선순위 큐를 적용하면 시간복잡도가 O((V + E) log V)가 된다.
최단 경로 찾기시 자주 쓰임

판별할 사항

  1. 모든 노드가 신호 받는데 걸리는 시간 => 시간 순으로 저장하기 위해 우선순위 큐 사용
  2. 모든 노드에 도달할 수 있는지 여부 (없으면 -1) => 결과 변수가 노드의 수와 같은지 확인

특징

  • Map.Entry를 사용하면 목록형 map을 반복문을 순회하듯 사용할 수 있다.
  • Map.Entry.comparingByValue()를 사용하여 정렬 순서를 지정할 수 있다.

풀이

  1. 담기 [2,1,1]를 Map<Integer, Map<Integer, Integer»에 담기
    => key 2 / k: 1, v: 1

  2. 우선순위 큐 준비
    Map.Entry.comparingByValue()를 사용하면 Value값을 기준으로 오름차순으로 정렬함
    new AbstractMap.SimpleEntry<>(k, 0) // k부터 시작이고 처음에는 거리가 0

  3. 순회 시작
    큐에 값이 없을 때까지 반복 큐의 값을 꺼내서 키와 값을 추출하고
    키가 결과맵에 없다면 추가하고 계속 진행
    키에 연관된 값들을 가져와서 비용을 계산해준 후 큐에 더한다. (큐에 값이 없을 때까지 반복)

  4. 검사
    순회가 끝나면 결과 값에 쌓인 것이 n개인지 확인한다.(맞다면 모두 순회한 것)
    같지 않다면 일부 노드에는 도달할 수 없음으로 판단한여 -1 반환

import java.util.*;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        // 1. 담기
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
        for(int[] time : times) {
            map.putIfAbsent(time[0], new HashMap<>());
            map.get(time[0]).put(time[1], time[2]);
        }

        // 2. 큐 준비 (도착지, 소요시간)
        Queue<Map.Entry<Integer, Integer>> q = new PriorityQueue<>(Map.Entry.comparingByValue());
        q.add(new AbstractMap.SimpleEntry<>(k, 0)); // 시작값 셋팅

        // 결과 배열 준비
        Map<Integer, Integer> result = new HashMap<>();

        // 순회 시작
        while(!q.isEmpty()) {
            Map.Entry<Integer, Integer> temp = q.poll();
            Integer dest = temp.getKey();
            Integer cost = temp.getValue();

            if(!result.containsKey(dest)) {
                result.put(dest, cost);
                if(map.containsKey(dest)) {
                    for(Map.Entry<Integer, Integer> t : map.get(dest).entrySet()) {
                    int alt = cost + t.getValue();
                    q.add(new AbstractMap.SimpleEntry<>(t.getKey(), alt));
                    }
                }
            }
        }

        // 검사
        if(result.size() == n) {
            // 가장 오래걸리는 지점의 소요시간 추출
            return Collections.max(result.values());
        }
        // 일부 노드에는 도달할 수 없음
        return -1;
    }
}

참고 도서 : 자바 알고리즘 인터뷰 with 코틀린 469p

You may also enjoy