백준 22870번: 산책(large) (Java)

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

22870번: 산책 (large)

문제

코로나로 인하여 확찐자가 되버려 오늘부터 산책을 하려고 한다. 산책할 경로를 정하려고 한다.

현재 있는 곳 S에서 출발하여 S와 다른 곳인 E를 찍고 다시 S로 돌아오는 경로로 만들려고 한다. 산책을 할 때 이미 갔던 정점을 또 가기 싫어 E에서 S로 올 때 S에서 E로 간 정점을 제외한 다른 정점으로 이동하려고 한다. 또한 산책 거리가 긴 것을 싫어하여 S에서 E로 가는 짧은 거리와 E에서 S로 가는 짧은 거리를 원한다.

정점 S에서 정점 E로 이동할 때, 짧은 거리의 경로가 여러개 나올 수 있다. 그 중, 정점 S에서 정점 E로 이동한 경로를 나열했을 때, 사전순으로 가장 먼저 오는 것을 선택한다.

예를 들어, 정점 1에서 정점 2로 이동한다고 했을 때, 짧은 거리의 경로가 1 4 3 2와 1 3 4 2가 있다고 가정을 해보자. 두 개의 경로중 사전순으로 먼저 오는 것은 1 3 4 2이므로 정점 1에서 정점 2로 가는 최단 경로 중 두 번째 것을 선택한다.

이와 같이 산책 경로를 정할 때, 산책 전체 경로의 거리(S에서 E로 가는 거리 + E에서 S로 가는 거리)를 구해보자.

입력

첫 번째 줄에는 정점의 개수 N과 두 정점 사이를 잇는 도로의 개수 M이 공백으로 구분되어 주어진다.

두 번째 줄부터 M+1 번째 줄까지 정점 A, B와 정점 A에서 정점 B로 가는 거리 C가 공백으로 구분되어 주어진다. 이때, 정점 A 정점 B는 양방향으로 이동해도 된다.

정점 A와 정점 B를 잇는 도로는 두개 이상 주어지지 않는다.

 M+2번째 줄에는 정점 S와 정점 E가 공백으로 구분되어 주어진다.

산책을 할 수 있는 경로가 있는 데이터만 주어진다.

출력

산책의 전체 경로의 길이를 출력한다.

제한

•  1≤N≤200,000
•  1≤M≤500,000
•  1≤S,E≤N
•  1≤C≤1,000

 

---

 

안 되는 풀이

다익스트라를 수행하면서, 최단 경로 중 이전 노드가 가장 작은 순으로 저장한 후 역순으로 살펴보면서 방문 노드를 체크하는 방법

 

반례(백준 mk9901님 글)

6 15
1 2 1
1 3 2
1 4 3
1 5 4
1 6 6
2 3 1
2 4 2
2 5 3
2 6 4
3 4 1
3 5 2
3 6 3
4 5 1
4 6 2
5 6 1
1 6
 

 

풀이

https://github.com/tony9402/FastCampus_Solution/blob/main/SET_5/06/Main.java에 정말 좋은 풀이가 있다. 풀이를 이해한 후 나름대로 재정립해서 적고자 했으나, 개선하면 할수록 베끼게 되는, 깔끔한 코드이다.

S->E까지 다익스트라하여 S에서 E까지 가는 최단 거리 x를 구한다., E->S에서 다익스트라 한번 해서 길을 저장한다. 이 후, S에서 시작하여,

(S까지 가는 거리) + (S에서 다음 점까지 가는 거리) + (E에서 다음 점까지 가는 거리) = (S에서 E까지 가는 거리)라면 해당 경로는 최단 경로 '후보'가 된다. 이런 후보들 중, 값이 가장 작은 정점이 '최단 경로로 갈 시 방문하는 노드'가 된다. 해당 노드를 적당히 기록해준다.

최단  노드는 - S와 E를 제외하고 - 체크를 한다. 이후 S를 다음 정점으로 할당하여, S가 E가 될때까지 반복문을 수행한다.

이후, 위에서 구한 'S에서 E로 오면서 이미 방문한 정점'은 방문하지 않도록 하여 E에서 S까지 다익스트라를 돌려 문제 조건을 만족하는 E에서 S까지의 최단 거리 y를 구한다.

정답은 x+y이다.

 

배운 점

새로운 풀이 방법을 익혔다: 경로 추적으로 풀면 안되는 걸 반례를 통해 느꼈다.

왠만한 다익스트라 문제는 다익스트라를 1~2번 쓰다보니, 그냥 main 함수 안에 때려박았는데 method로 빼내니 코드가 훨씬 더 깔끔해지더라.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
    static long[] dS, dE;
    static final Long INF = Long.MAX_VALUE;
    static Set<Integer> visited;
    static List<List<Edge>> graph;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        dS = new long[N+1];
        dE = new long[N+1];
        graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<Edge>());
            dS[i] = dE[i] = INF;
        }
        
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());
            graph.get(A).add(new Edge(B, C));
            graph.get(B).add(new Edge(A, C));
        }
        
        st = new StringTokenizer(br.readLine());
        int S = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());
        
        long ans = 0;
        visited = new HashSet<Integer>();
        dijkstra(dS, S);
        dijkstra(dE, E);
        ans += dS[E];
        
        eraseNode(S, E);
        Arrays.fill(dE, Long.MAX_VALUE);
        dijkstra(dE, E);
        
        ans += dE[S];
        System.out.println(ans);
    }
    
    static class Edge implements Comparable<Edge> {
        int loc;
        long dist;
 
        public Edge(int loc, long dist) {
            this.loc = loc;
            this.dist = dist;
        }
 
        public int compareTo(Edge o) {
            return Long.compare(this.dist, o.dist);
        }
    }
    
    static void dijkstra(long[] dist, int start) {
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(start, 0));
        dist[start] = 0;
        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            if (dist[cur.loc] < cur.dist) continue;
            for (Edge nxt: graph.get(cur.loc)) {
                if (visited.contains(nxt.loc)) continue;
                if (dist[nxt.loc] <= cur.dist + nxt.dist) continue;
                dist[nxt.loc] = cur.dist + nxt.dist;
                pq.offer(new Edge(nxt.loc, dist[nxt.loc]));    
            }
        }
    }
    
    static void eraseNode(int S, int E) {
        int start = S, pre = S;
        while (start != E) {
            int min = Integer.MAX_VALUE;
            for (Edge nxt: graph.get(start)) {
                if (pre == nxt.loc) continue;
                if (dS[start] + nxt.dist + dE[nxt.loc] == dS[E]) {
                    min = Math.min(min, nxt.loc);
                }
            }
            pre = start;
            start = min;
            if (start != E) visited.add(start);
        }
    }
}