[다익스트라] 백준 1504번 특정한 최단 경로 - JAVA

 

 

오랜만에 다익스트라 푸니까

원리 다 까먹어버림

 

---

1. 출처

---

 

1504번: 특정한 최단 경로

 

• 1~N까지 가는 최단 경로의 거리를 구하는 문제
• 최단 경로를 구하는 과정에서 필수 2가지 노드를 꼭 거쳐야함

 

 

---

2. 설계

---

 

2-1) 다익스트라의 원리

다익스트라 알고리즘은 출발지에서 연결된 모든 도착지에 대해 최단 거리를 계산한다. (연결되지 않으면 계산하지 않음)

때문에 출발지 지정이 중요하다.

 

[다익스트라 기본 코드]

public static int Dijkstra(int startNode){
        Arrays.fill(dist, INF);
        boolean[] visited = new boolean[N+1];//정점은 1부터 시작
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        
        pq.offer(new Edge(startNode, 0));
        dist[startNode] = 0;
        
        while(!pq.isEmpty()){
            Edge cur = pq.poll();

            if(visited[cur.num]) continue;
            
            visited[cur.num] = true;
            
            for(int i=0; i<adj[cur.num].size(); i++){
                Edge next = adj[cur.num].get(i);

                if(dist[next.num]>dist[cur.num]+next.len){
                    dist[next.num] = dist[cur.num]+next.len;
                    pq.offer(new Edge(next.num, dist[next.num]));
                }
            }
        }
    }

 

우선순위큐에서 나온 경로는 선택된 경로라고 본다.

 

 

2-2) 문제 푸는 방법

다익스트라 변형 문제이다.

꼭 가야하는 경로가 node1, node2라고 한다면

 

1 -> node1 으로 다익스트라를 돌려 node1의 최단 거리를 구한다.

node1 -> node2 로 다익스트라를 돌려 node2의 최단 거리를 구한다.

node2 -> N 으로 다익스트라를 돌려 N의 최단 거리를 구한다.

그러면 1 -> node1 -> node2 -> N의 최단 거리를 최종적으로 구할 수 있는 것이다.

 

 

그런데 1 노드에서 node2와의 최단 거리를 구하고 node1로도 갈 수도 있다.

1 -> node2 -> node1 -> N의 최단 거리도 구해야 하는 것이다.

 

 

정리하자면, 아래 2가지 경로의 최단 거리를 구해야 하는 것이다.

• 1 -> node1 -> node2 -> N
• 1 -> node2 -> node1 -> N

//1 -> Node1 -> Node2 -> N
int ans1 = 0;
ans1 += Dijkstra(1, essential_path[0]);
ans1 += Dijkstra(essential_path[0], essential_path[1]);
ans1 += Dijkstra(essential_path[1], N); 
    
//2 -> Node2 -> Node1 -> N
int ans2 = 0;
ans2 += Dijkstra(1, essential_path[1]);
ans2 += Dijkstra(essential_path[1], essential_path[0]);
ans2 += Dijkstra(essential_path[0], N);

 

 

만약 1 ~ N의 최단 거리를 구하는 중 연결되지 않는 경로가 있다면 INF(간선개수 20만 * 거리 최대값  1000) 값이 중도에 더해질 것이다.

• 1 -> node1 -> node2 -> N 의 모든 경로가 연결되지 않는다면, 당연히 
• 1 -> node2 -> node1 -> N 이 경로도 모두 연결되지 않는다.

int ans = ans1>=INF && ans2>=INF ? -1 : Math.min(ans1, ans2);
System.out.println(ans);

 

 

+어쩐일인지 아래처럼 정답을 출력하면 초장부터 오답이 나온다.

if(ans1>=INF && ans2>=INF) System.out.println(-1);
else System.out.println(Math.min(ans1, ans2));

 

 

 

---

3. 전체 코드

---

import java.util.*;
import java.io.*;

// 1번 정점에서 N번 정점으로 이동할 때,
// 주어진 두 정점을 반드시 거치면서 최단 경로로 이동

class Main {
    static int N;
    static List<Edge>[] adj;
    static int[] essential_path = new int[2];

    static int[] dist;
    static int INF = 200000 * 1000;

    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String NE = br.readLine();
        StringTokenizer st = new StringTokenizer(NE, " ");
        N = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        adj = new ArrayList[N+1];//정점 1부터 시작
        for(int i=0; i<N+1; i++){
            adj[i] = new ArrayList<>();
        }

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

            adj[a].add(new Edge(b, c));
            adj[b].add(new Edge(a, c));
        }

        String paths = br.readLine();
        st = new StringTokenizer(paths, " ");
        essential_path[0] = Integer.parseInt(st.nextToken());
        essential_path[1] = Integer.parseInt(st.nextToken());

        //입력 끝

        dist = new int[N+1]; //1부터 시작
        
        //1 -> Node1 -> Node2 -> N
        int ans1 = 0;
        ans1 += Dijkstra(1, essential_path[0]);
        ans1 += Dijkstra(essential_path[0], essential_path[1]);
        ans1 += Dijkstra(essential_path[1], N); 
    
        //2 -> Node2 -> Node1 -> N
        int ans2 = 0;
        ans2 += Dijkstra(1, essential_path[1]);
        ans2 += Dijkstra(essential_path[1], essential_path[0]);
        ans2 += Dijkstra(essential_path[0], N);

        int ans = ans1>=INF && ans2>=INF ? -1 : Math.min(ans1, ans2);
        System.out.println(ans);
    }

    public static int Dijkstra(int startNode, int endNode){
        Arrays.fill(dist, INF);
        boolean[] visited = new boolean[N+1];//정점은 1부터 시작
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        
        pq.offer(new Edge(startNode, 0));
        dist[startNode] = 0;
        
        while(!pq.isEmpty()){
            Edge cur = pq.poll();

            if(visited[cur.num]) continue;
            
            visited[cur.num] = true;
            
            for(int i=0; i<adj[cur.num].size(); i++){
                Edge next = adj[cur.num].get(i);

                if(dist[next.num]>dist[cur.num]+next.len){
                    dist[next.num] = dist[cur.num]+next.len;
                    pq.offer(new Edge(next.num, dist[next.num]));
                }
            }
        }

        return dist[endNode];
    }

    public static class Edge implements Comparable<Edge>{
        int num;
        int len;
        public Edge(int num, int len){
            this.num = num;
            this.len = len;
        }

        @Override
        public int compareTo(Edge o){
            return this.len>o.len?1:-1;
        }
    }    
}