Yunseok Byeon

Yunseok Byeon

Motivational Speaker

백준 1504번 : 특정한 최단 경로

1. 문제 설명 (1504)

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

2. 분류

3. 풀이

전형적인 Dijkstra 알고리즘을 활용한 문제이다.

Dijkstra 알고리즘으로는 이전에 1753번: 최단경로를 풀어봤는데, 이 문제와 상당히 유사하다.
다만 몇 가지 차이점이 있는데, 다음과 같다.

  1. 양 방향 가중치가 c 로 동일하다.
    • 말 그대로 두 정점의 양 방향 으로 모두 이동할 수 있다. 최단 경로를 계산할 때 고려해야 할 것이다.
  2. v1, v2 라는 정점을 무조건 지나야 한다.
    • 최단경로를 구할 때, 1 -> v1 -> v2 -> N, 1 -> v2 -> v1 -> N 두 가지 경우를 모두 고려해야 한다.
    • 두 경우에서의 최단 경로를 구하면 되므로, Math.min 으로 최솟값 을 반환하면 된다.

따라서 LinkedList 와 PriorityQueue 를 활용해 그래프를 구현하고, Node 클래스를 정의했다.
경로가 없는 경우를 고려해, Integer.MAX_VALUE 를 활용해 경로가 없는 경우를 판별했다.

4. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
import java.io.*;
import java.util.*;
 
public class Q1504 {
 
    static LinkedList<Node> list[];
    static int distance[];
    static int N, E;
    
    public static void main(String args[]) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] temp = br.readLine().split(" ");
        N = Integer.parseInt(temp[0]);
        E = Integer.parseInt(temp[1]);
        list = new LinkedList[N+1];
        distance = new int[N+1];
        for(int i = 1; i <= N; i++)
            list[i] = new LinkedList<>();
        
        for(int i = 0; i < E; i++) {
            String[] grp = br.readLine().split(" ");
            int n1 = Integer.parseInt(grp[0]);
            int n2 = Integer.parseInt(grp[1]);
            int c = Integer.parseInt(grp[2]);
            list[n1].add(new Node(n2, c));
            list[n2].add(new Node(n1, c));
        }
        
        String[] v1v2 = br.readLine().split(" ");
        int v1 = Integer.parseInt(v1v2[0]);
        int v2 = Integer.parseInt(v1v2[1]);
        
        long answer1 = 0;
        long answer2 = 0;
        
        //v1 -> v2
        answer1 += dijkstra(1, v1);
        answer1 += dijkstra(v1, v2);
        answer1 += dijkstra(v2, N);
        
        //v2 -> v1
        answer2 += dijkstra(1, v2);
        answer2 += dijkstra(v2, v1);
        answer2 += dijkstra(v1, N);
        
        if(Math.min(answer1, answer2) >= Integer.MAX_VALUE)
            bw.write("-1");
        else
            bw.write(Math.min(answer1, answer2)+"");
 
        bw.flush();
        bw.close();
    }
    
    public static int dijkstra(int start, int end) {
        distance = new int[N+1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(start, 0));
        
        while(!pq.isEmpty()) {
            Node now = pq.poll();
            int number = now.number;
            int weight = now.weight;
            if(distance[number] < weight)
                continue;
            
            for(int i = 0; i < list[number].size(); i++) {
                int number2 = list[number].get(i).number;
                int weight2 = list[number].get(i).weight + weight;
                if(distance[number2] > weight2) {
                    distance[number2] = weight2;
                    pq.add(new Node(number2, weight2));
                }
            }
        }
        return distance[end];
    }
    
    static class Node implements Comparable<Node> {
        int number, weight;
        
        Node(int n, int w) {
            this.number = n;
            this.weight = w;
        }
        
        @Override
        public int compareTo(Node n) {
            return weight - n.weight;
        }
    }
    
}
cs


5. 결과

result image

1528ms로 잘 작동한다.

댓글남기기

참고