배달

class Solution {
    private static int maps[][];
    private static int MAX_VALUE = 500001;
    public static void Input(int i, int j, int w) {
        if (maps[i][j] > w) {
            maps[i][j] = w;
            maps[j][i] = w;
        }
    }
 
    public static void Dijkstra(int[][] road, int[] distance, int N, int v) {
        boolean[] check = new boolean[N + 1];
        int MAX_VALUE = 500001;
 
        // 거리 값 초기화
        for (int i = 1; i < N + 1; i++) {
            distance[i] = MAX_VALUE;
        }
 
        // 시작노드 값 초기화.
        distance[v] = 0;
        check[v] = true;
 
        // 연결된 노드 거리 값 갱신
        for (int i = 1; i < N + 1; i++) {
            if (!check[i] && maps[v][i] != 0) {
                distance[i] = maps[v][i];
            }
        }
 
        // 다익스트라 알고리즘 반복 횟수는 N-1
        for (int a = 0; a < N - 1; a++) {
            int min = MAX_VALUE;
            int min_index = -1;
 
            // 최소 값 인덱스 찾기
            for (int i = 1; i < N + 1; i++) {
                if (!check[i] && distance[i] != MAX_VALUE) {
                    if (distance[i] < min) {
                        min = distance[i];
                        min_index = i;
                    }
                }
            }
            // 최소 거리 갱신
            check[min_index] = true;
            for (int i = 1; i < N + 1; i++) {
                if (!check[i] && maps[min_index][i] != 0) {
                    if (distance[i] > distance[min_index] + maps[min_index][i]) {
                        distance[i] = distance[min_index] + maps[min_index][i];
                    }
                }
            }
        }
    }
    
    public int solution(int N, int[][] road, int K) {
        int answer = 0;
        int distance[] = new int[N + 1];
        maps = new int[N + 1][N + 1];
        // map 초기화
        for (int i = 1; i < N + 1; i++)
            for (int j = 1; j < N + 1; j++)
                maps[i][j] = MAX_VALUE;
        for (int i = 0; i < road.length; i++)
            Input(road[i][0], road[i][1], road[i][2]);
        Dijkstra(road, distance, N, 1);
 
        for (int i = 1; i < N + 1; i++) {
            if (distance[i] <= K)
                answer++;
        }
        return answer;
    }
}

다익스트라 알고리즘으로 해결하였다.

여기서 다중 경로가 입력되는 경우가 있다.

이 때 기존 경로보다 해당 경로가 더 멀 경우에 갱신하지 않도록 예외 처리를 해주어야 한다.

 

다익스트라 알고리즘에 대해 참고한 사이트는 아래와 같다.

참고 사이트 : https://bumbums.tistory.com/4