(BOJ)1504 특정한 최단경로

1504 특정한 최단 경로

백준 특정한 최단 경로

 

Tip

• 다익스트라 알고리즘 활용

  • 다익스트라 알고리즘은 출발점에서 모든 정점에 대한 최단거리를 구하는 알고리즘이다.
  • 꼭 들려야 하는 정점을 끝나는 지점으로 하는 다익스트라를 여러번 돌려 원하는 값을 찾을 수 있다.

 

 

CODE

​x
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
​
public class BOJ_1504 {
​
    static final int INF = 800000;
    static List<Edge>[] map;
    static int node;
    static int edge;
​
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
​
        node = Integer.parseInt(st.nextToken());
        edge = Integer.parseInt(st.nextToken());
​
        map = new ArrayList[node+1];
​
        for(int i = 1; i <= node ; i++){
            map[i] = new ArrayList<>();
        }
​
        for(int i = 1; i <= edge ; i++){
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
​
            map[from].add(new Edge(to, value));
            map[to].add(new Edge(from, value));
        }
​
        st = new StringTokenizer(br.readLine());
​
        int mid1 = Integer.parseInt(st.nextToken());
        int mid2 = Integer.parseInt(st.nextToken());
​
        int result1 = dijk(1, mid1) + dijk(mid1, mid2) + dijk(mid2, node);
        int result2 = dijk(1, mid2) + dijk(mid2, mid1) + dijk(mid1, node);
​
        if(result1 >= INF && result2 >= INF){
            System.out.println(-1);
            return;
        }
​
        if (result1 > result2) {
            System.out.println(result2);
        } else {
            System.out.println(result1);
        }
    }
​
    static int dijk(int start, int finish){
​
        if(start == finish) return 0;
​
        int[] dist = new int[node+1];
        Arrays.fill(dist, INF);
        dist[start] = 0;
​
        Queue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(start, 0));
​
        while(!pq.isEmpty()){
            Edge current = pq.poll();
            if(current.to==finish) return dist[current.to];
​
            for(int i = 0; i < map[current.to].size(); i++){
                Edge next = map[current.to].get(i);
​
                if(dist[next.to] > dist[current.to] + next.value){
                    dist[next.to] = dist[current.to] + next.value;
                    pq.add(new Edge(next.to, dist[next.to]));
                }
            }
        } //while
​
        return INF;
    }
​
    static class Edge implements Comparable<Edge>{
        int to;
        int value;
​
        public Edge(int to, int value) {
            this.to = to;
            this.value = value;
        }
​
        @Override
        public int compareTo(Edge o) {
            return this.value>o.value ? 1:-1;
        }
    }
}
​

 

DEBUG

다익스트라 알고리즘을 구현한 부분에서 break 부분을 잘못해서 문제를 풀지 못했다. 백준에 질문한 결과 문제에서 벗어나는 조건을 확인할때는 다음포인트보다는 현재지점에서 검사하는것이 더좋다는 답변을 받았다.

if(Current.to == finish) 부분이 원래 for문 안쪽에 if(next.to == finish) 로구현되어있었다. for문 안에 있으면 더 빨리 도달점을 찾을 수 있을 거라고 생각했다. 하지만, 다익스트라 알고리즘상 현재 점이 finish점일때 벗어나는 것이 맞다. 업데이트 될 가능성이 있기 때문이다.

다익스트라 알고리즘에 대해서 정확하게 인지 하지 못했던거 같다.