[BOJ] 백준 9370 미확인 도착지 - Python/Java

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

9370번: 미확인 도착지

 

[해설] 

이 문제는 다익스트라 알고리즘을 기반으로 해결할 수 있으며 기본 아이디어는 다음과 같습니다.

 

경로 1) (시작점 → g) + (g → h) + (h → 도착점)

경로 2) (시작점 → h) + (h → g) + (g → 도착점)

 

위 두 가지 경로 중에서 비용이 더 적은 경로와 (시작점 → 도착점)을 직접 구한 비용이 같다면 해당 도착점은 반드시 (g, h) 도로를 지난다고 볼 수 있습니다.

 

그런데 목적지 후보 각각에 대해 위 값을 계산하기 위해 다익스트라 알고리즘을 매번 수행하게 되면 시간초과가 발생할 수밖에 없습니다. 다익스트라 알고리즘이 기본적으로 O(ElogV) 시간복잡도를 가지는데, O(tc * ElogV * 목적지 후보의 수)를 계산하게 되기 때문이죠.

 

따라서, 목적지 후보를 관찰하기 전에 다익스트라 알고리즘을 총 세 번만(시작점을 s, g, h로 설정) 수행한 뒤 다익스트라 알고리즘을 통해 리턴받은 거리 배열을 통해 거리를 계산해야 합니다. 이 부분에 대한 설명은 코드로 확인하는 것이 더 직관적으로 이해될 것이라 생각합니다.

 

결국, 이 문제의 핵심은 두 가지입니다.

1) (g, h) 경로를 지나서 도착하는 목적지는 어떻게 판별할 것인가?

2) 다익스트라 알고리즘을 반복적으로 수행하지 않고, 구하고자 하는 구간의 거리를 구할 수 있는가?

 

풀이는 아래와 같습니다.

 

[풀이 - 파이썬]

import sys, heapq
input = sys.stdin.readline

def dijkstra(graph, start):
    distance = [int(1e10)] * (n+1) # 처음 거리는 모두 무한대로 초기화
    distance[start] = 0

    pq = []
    heapq.heappush(pq, (0, start))
    while pq:
        currCost, currPos = heapq.heappop(pq)
        if currCost < distance[currPos]: continue

        for nextCost, nextPos in graph[currPos]:
            if currCost + nextCost < distance[nextPos]:
                distance[nextPos] = currCost + nextCost
                heapq.heappush(pq,(currCost+nextCost, nextPos))

    return distance

tc = int(input()) # 테스트 케이스의 개수
for _ in range(tc):
    n, m, t = map(int, input().split()) # 교차로, 도로, 목적지 후보의 개수
    s, g, h = map(int, input().split()) # s는 출발지이고 g,h는 냄새를 맡은 도로
    
    graph = [[] for _ in range(n+1)]
    dest = []
    g_to_h = 0
    for _ in range(m):
        a, b, d = map(int, input().split()) # a, b 사이에 거리가 d인 도로 존재
        graph[a].append((d,b))
        graph[b].append((d,a))
        if (a == g and b == h) or (a == h and b == g): g_to_h = d # g, h 사이의 거리

    for _ in range(t): dest.append(int(input())) # t개의 목적지 후보

    # (s -> d) = (s -> g) + (g -> h) + (h -> d)
    # (s -> d) = (s -> h) + (h -> g) + (g -> d)
    answer = []
    distance_s = dijkstra(graph, s) # 시작점 s로부터 다른 지점까지의 거리
    distance_g = dijkstra(graph, g) # 시작점 g로부터 다른 지점까지의 거리
    distance_h = dijkstra(graph, h) # 시작점 h로부터 다른 지점까지의 거리

    for d in dest:
        totalCost = distance_s[d]
        s_to_g, h_to_d = distance_s[g], distance_h[d]
        s_to_h, g_to_d = distance_s[h], distance_g[d]
        if totalCost == g_to_h + min(s_to_g + h_to_d, s_to_h + g_to_d):
            answer.append(d)
    for x in sorted(answer): print(x, end = " ")

 

 

[풀이 - 자바]

package PS;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class B_9370 {
    static int tc, n, m, t, s, g, h;
    static int g_to_h, s_to_g, h_to_d, s_to_h, g_to_d;
    static int[] distance_s, distance_g, distance_h;


    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        tc = Integer.parseInt(br.readLine());
        while(tc-- > 0){
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            t = Integer.parseInt(st.nextToken());

            st = new StringTokenizer(br.readLine());
            s = Integer.parseInt(st.nextToken());
            g = Integer.parseInt(st.nextToken());
            h = Integer.parseInt(st.nextToken());

            ArrayList<ArrayList<Edge>> graph = new ArrayList<>();
            ArrayList<Integer> dest = new ArrayList<>();
            ArrayList<Integer> answer = new ArrayList<>();

            for(int i = 0; i < n+1; i++){   // 그래프 초기화
                graph.add(new ArrayList<>());
            }

            for(int i = 0; i < m; i++){ // 그래프 입력받기, g to h 거리 저장
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int d = Integer.parseInt(st.nextToken());
                if((a == g && b == h) || (a == h && b == g)) g_to_h = d;
                graph.get(a).add(new Edge(d, b));
                graph.get(b).add(new Edge(d, a));
            }
            // 목적지 후보 입력받기
            for (int i = 0; i < t; i++) dest.add(Integer.parseInt(br.readLine()));

            distance_s = dijkstra(graph, s); // 시작점 s로부터 다른 지점까지의 거리
            distance_g = dijkstra(graph, g); // 시작점 g로부터 다른 지점까지의 거리
            distance_h = dijkstra(graph, h); // 시작점 h로부터 다른 지점까지의 거리
            for(int d : dest){
                int totalCost = distance_s[d];
                s_to_g = distance_s[g];
                h_to_d = distance_h[d];
                s_to_h = distance_s[h];
                g_to_d = distance_g[d];
                if(totalCost == g_to_h + Math.min(s_to_g + h_to_d, s_to_h + g_to_d)){
                    answer.add(d);
                }
            }
            Collections.sort(answer);
            answer.forEach((o) -> System.out.print(o + " "));
        }

    }

    public static int[] dijkstra(ArrayList<ArrayList<Edge>> graph, int start){
        int[] distance = new int[n+1];
        for(int i = 0; i < n+1; i++) distance[i] = 10000000;
        distance[start] = 0; // 시작 지점 값은 0으로 초기화

        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(0, start));

        while (!pq.isEmpty()) {
            Edge e = pq.poll();
            int currCost = e.cost;
            int currPos = e.node;
            if(currCost < distance[currPos]) continue;

            for(Edge next : graph.get(currPos)){
                int nextCost = next.cost;
                int nextPos = next.node;
                if(distance[nextPos] > currCost + nextCost){
                    distance[nextPos] = currCost + nextCost;
                    pq.add(new Edge(currCost + nextCost, nextPos));
                }
            }
        }
        return distance;
    }

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

        @Override
        public int compareTo(Edge other){
            return this.cost - other.cost;
        }
    }
}