[Algorithm] 백준_특정한 최단 경로_1504번 (JAVA)

📝문제

https://www.acmicpc.net/problem/1504

특정한 최단 경로 1504번

티어: 골드 4

💡풀이

문제 유형

다익스트라

 

걸린 시간

100분

 

시간 복잡도

O((V + E) log V)

 

풀이 방법 도출

1. bfs로 접근했다가 도저히 답이 안 나와서 다익스트라 알고리즘이라는 힌트를 얻고 풀이를 하였다.
2. 다익스트라 알고리즘이란 가중치가 있는 그래프에서 최단 거리를 찾기 위한 알고리즘으로, 우선순위 큐를 활용한다.
3. 해당 문제는 1번 노드에서 시작해 꼭 거쳐야 하는 노드 v1,v2를 지나 n번 노드까지 도착해야한다.
4. 즉 다익스트라 함수를 구현하여
5. (1번 -> v1번 노드의 최소 거리) + (v1번 -> v2번 노드의 최소 거리) + (v2번 -> N번 노드의 최소 거리)
6. 또는
7. (1번 -> v2번 노드의 최소 거리) + (v2번 -> v1번 노드의 최소 거리) + (v1번 -> N번 노드의 최소 거리)
8. 중 최솟값이 정답이 된다.
9. 다익스트라 함수 구현은 다음과 같다.
   1. 경로의 길이를 기준으로 오름차순 정렬을 갖는 우선순위 큐를 선언한다.
   2. 최소 거리를 담는 dist[] 배열을 선언하고 int 최대값으로 초기화한다.
   3. 이때 시작지점은 0으로 초기화한다.
   4. 큐에 현재 노드와 현재 거리 0을 넣고
   5. 큐가 빌 때까지 반복문을 돌린다.
   6. 큐에서 꺼낸 노드(now)와 거리(cost)를 변수에 담고
   7. 현재 노드와 인접한 노드를 찾는다.
   8. 현재 거리와 인접한 노드의 거리의 합이 dist[인접 노드]보다 작다면 dist[인접노드]를 갱신해준다.
   9. 큐에 인접 노드와 인접 노드까지의 거리를 담고 반복한다.

import java.util.*;
import java.io.*;
class Main{
    static int N;
    static ArrayList<Node>[] graph;
    static int INF = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        graph = new ArrayList[N+1];
        for(int i = 0; i <= N; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i = 0; i < E; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            graph[a].add(new Node(b,c));
            graph[b].add(new Node(a,c));
        }

        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken());
        int v2 = Integer.parseInt(st.nextToken());

        int[] dist_1 = dijkstra(1);
        int[] dist_v1 = dijkstra(v1);
        int[] dist_v2 = dijkstra(v2);

        long route1 = (long) dist_1[v1] + dist_v1[v2] + dist_v2[N];
        long route2 = (long) dist_1[v2] + dist_v2[v1] + dist_v1[N];

        long answer = Math.min(route1, route2);

        System.out.println(answer >= INF ? -1 : answer);

    }
    public static int[] dijkstra(int start){
        PriorityQueue<Node> pq = new PriorityQueue<>((a,b)->a.d);
        int[] dist = new int[N+1];
        Arrays.fill(dist, INF);
        dist[start] = 0;
        pq.add(new Node(start, 0));

        while(!pq.isEmpty()){
            Node current = pq.poll();
            int now = current.x;
            int cost = current.d;

            for(Node next : graph[now]){
                int newCost = cost + next.d;
                if(newCost < dist[next.x]){
                    dist[next.x] = newCost;
                    pq.add(new Node(next.x, newCost));
                }
            }
        }
        return dist;
    }
}
class Node{
    int x;
    int d;
    public Node(int x, int d){
        this.x = x;
        this.d = d;
    }
}

 

🤔Review

다익스트라 알고리즘 구현에 아직 익숙치 않다,,헷갈리고 어려워ㅠ익숙해지는 그날까지 ㅎㅇㅌ