[JAVA] 프로그래머스 LEVEL3 부대 복귀

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

프로그래머스

코딩테스트 연습 > 연습문제 > 부대복귀

 

난이도: LEVEL3

알고리즘 유형: 다익스트라 

문제 접근

문제 요구사항

목적지는 정해져 있고 

출발지는 최대 500개인 문제이다.

모든 출발지에서 목적지까지의 최단거리를 구한다.

특정 출발지는 목적지까지 도달 못하는 경우가 있다 해당 케이스는 최단거리를 -1로 반환한다.  

 

다익스트라 알고리즘 

다익스트라 알고리즘은 어떤 특정 정점부터 각 정점까지의 최단거리를 구하는 데 있어서 특화된(효율적인) 알고리즘

이번 문제를 어떻게 다익스트라 알고리즘으로 풀 수 있을까?

발상의 전환이다. 

우리는 모든 출발지부터 목적지까지의 최단거리를 구해야 한다.

하지만 각 간선은 무조건 양방향이고 각 간선의 가중치는 1로 고정이다.

그럼 목적지를 기준으로 다익스트라 알고리즘으로 각 정점까지의 최단 거리를 구하면 된다. 

그럼 각 정점에는 우리가 구할려는 출발지도 포함되어 있다. 

출발지 ↔ 목적지(최단거리)  == 목적지 ↔  출발지 (최단거리)

이렇게 간단하게 다익스트라 1번으로 모든 출발지부터 목적지까지의 최단거리를 구한 것이다.

 

각 출발지부터 목적지까지 최대 500번 다익스트라에서 1번으로 줄일 수 있다.

아마 문제 의도가 다익스트라가 맞다면 아마 500번 다익스트라나 다른 알고리즘 플로이드 BFS는 절대 통과 못할 것이다. 

정답 코드 

import java.util.*;
class Solution {
    static ArrayList<Integer>[] graph; // 그래프를 인접 리스트로 저장
    static int [] answer; // 최종 결과를 저장할 배열
    static int [] min; // 목적지로부터 각 정점까지의 최단 거리를 저장할 배열

    public int[] solution(int n, int[][] roads, int[] sources, int destination) {
        // 그래프 초기화
        graph = new ArrayList[n+1];
        for(int i = 0; i <= n; i++){
            graph[i] = new ArrayList<>();
        }
        
        answer = new int [sources.length];
        
        // 양방향 그래프 생성
        for(int i = 0; i < roads.length; i++){
            graph[roads[i][0]].add(roads[i][1]);
            graph[roads[i][1]].add(roads[i][0]);
        }

        // 최단 거리 배열 초기화
        min = new int [n+1];
        Arrays.fill(min, Integer.MAX_VALUE); // 모든 거리를 무한대로 설정
        dijkstra(destination); // 목적지에서 다익스트라 알고리즘 실행

        // 결과 계산
        for(int i = 0; i < sources.length; i++){
            if(min[sources[i]] == Integer.MAX_VALUE){
                answer[i] = -1; // 도달할 수 없는 경우
            } else {
                answer[i] = min[sources[i]]; // 최단 거리 값 반환
            }
        }

        return answer;
    }

    public static void dijkstra(int start){ // 목적지에서 출발하는 다익스트라
        PriorityQueue<int []> q = new PriorityQueue<>((o1,o2) -> o1[1] - o2[1]); // 거리 기준 우선순위 큐
        min[start] = 0; // 목적지까지의 거리는 0
        q.add(new int [] {start, 0});

        while(!q.isEmpty()){
            int[] cur = q.poll(); // 현재 정점과 거리
            if(min[cur[0]] != cur[1]) continue; // 이미 더 짧은 경로가 있으면 패스
            for(int i = 0; i < graph[cur[0]].size(); i++){
                int next = graph[cur[0]].get(i);
                if(min[next] > cur[1] + 1){ // 더 짧은 경로를 발견한 경우
                    min[next] = cur[1] + 1;
                    q.add(new int [] {next, cur[1] + 1}); // 다음 정점으로 이동
                }
            }
        }
    }
}