[BOJ] 백준 1719 택배 - Python/Java

문제

1719번: 택배

해설

이 문제는 기본적으로 다익스트라 알고리즘을 이용해서 풀 수 있는데요. 문제에서 요구하는 X 지점에서 Y 지점을 최단거리로 이동할 때 첫번째로 방문하는 지점을 구하기 위해서는 필연적으로 이동하는 '경로' 역시 저장해줘야 하는 문제입니다.

 

한편, 다익스트라 알고리즘에서 경로를 저장하는 법은 Dictionary나 Map을 이용하면 쉽게 구현할 수 있습니다. 기본적으로 각 지점의 이전 지점만을 저장하기 때문에 1:1로 매핑이 될 수밖에 없기 때문인데요. 따라서, 어떤 지점 X에서 최단거리를 갱신할 수 있는 지점 Y로 이동한다면 Y입장에서 이전 지점(Parent)은 X로 저장해주기만 하면 됩니다.

 

자세한 설명은 아래 문제를 풀 때 자세히 설명했으니, 참고해주세요.

[백준(파이썬/Python)] 11779_최단경로 구하기2 - 다익스트라

 

경로를 저장하는 법은 위에서 설명했으니, 다시 문제로 돌아오겠습니다.

 

이 문제에서 K번째 노드를 시작점으로 다익스트라 알고리즘을 돌리게 되면, 그 결과값으로 K번째 노드에서 다른 모든 노드로 가는 최단경로(distance)와 각 지점의 이전 경로(parents)를 알 수 있습니다.

 

한 가지 예시를 들어보겠습니다. 만약 1번 노드에서 다익스트라를 수행한 결과, parents 정보가 아래와 같다고 해보겠습니다.

 

parents = ['1': -1, '2': 1, '3': 1, '4': 3, '5': 2, '6': 2] (자기 자신의 부모는 -1로 설정합니다)

 

parents를 해석해보면 1번 노드는 자기 자신이기 때문에 -1을 갖고, 2번 노드는 1번 노드가 부모임을 알 수 있습니다. 마찬가지로 3번 노드도 1번 노드가 부모이며, 4번 노드는 3번 노드가 자신의 부모입니다.

 

따라서 1번 노드에서 출발해 4번 노드로 갈 때 가장 먼저 들러야 하는 곳은 3번 노드인데요. 이는 부모를 역으로 추적해보면 4 -> 3 -> 1의 순서가 되는데, 3번 노드의 부모가 1번 노드이기 때문에 가장 먼저 들려야 하는 곳이 3번 노드가 되는 것입니다.

 

 

이를 토대로 구현한 풀이는 아래와 같습니다.

 

 

풀이 - 파이썬

import sys, heapq
from collections import defaultdict
input = sys.stdin.readline

def dijkstra(start):
    parents = defaultdict() # 각 지점의 이전 지점을 저장하는 리스트
    for i in range(1, n+1): parents[i] = i
    distance = [int(1e10)] * (n+1) # 각 지점까지의 거리를 저장하는 리스트
    distance[start] = 0

    pq = []
    heapq.heappush(pq, (0, start))
    while pq:
        currCost, currPos = heapq.heappop(pq)
        # 이미 방문한 적이 있다면 무시
        if distance[currPos] < currCost: continue
        
        for next in graph[currPos]:
            nextCost, nextPos = next[0], next[1]
            if currCost + nextCost < distance[nextPos]:
                heapq.heappush(pq, (currCost + nextCost, nextPos))
                distance[nextPos] = currCost + nextCost
                parents[nextPos] = currPos
    # 각 지점에 가기 위해 첫번째로 방문하는 곳을 출력            
    for i in range(1, n+1):
        if i == start: # 목적지가 자신이면 "-" 출력
            print("-", end = " ")
        else: # 목적지가 다른 곳이면 parents에서 탐색
            curr = i
            while(parents[curr] != start):
                curr = parents[curr]
            print(str(curr), end = " ")
    print()

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((c, b))
    graph[b].append((c, a))

for i in range(1, n+1):
    dijkstra(i)

풀이 - 자바

package PS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class B_1719 {
    static int n, m;
    static List<Edge>[] graph;
    static int[][] answer;

    static void dijkstra(int start){
        int[] distance = new int[n+1]; // 각 지점까지의 거리를 저장하는 리스트
        Map<Integer, Integer> parents = new HashMap<>(); // 각 지점의 이전 지점을 저장하는 리스트
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;
        for(int c = 1; c < n+1; c++) parents.put(c, -1);

        PriorityQueue<Edge> pq = new PriorityQueue<>((x, y) -> x.cost - y.cost);
        pq.add(new Edge(start, 0));
        while(!pq.isEmpty()){
            Edge e = pq.poll();
            int currCost = e.cost, currPos = e.vertex;
            // 이미 방문한 적이 있다면 무시
            if(distance[currPos] < currCost) continue;
            
            for(Edge next : graph[currPos]){
                int nextCost = next.cost, nextPos = next.vertex;
                if(currCost + nextCost < distance[nextPos]){
                    pq.add(new Edge(nextPos,currCost + nextCost));
                    distance[nextPos] = currCost + nextCost;
                    parents.replace(nextPos, currPos);
                }
            }
        }
        // 각 지점에 가기 위해 첫번째로 방문하는 곳을 출력
        StringBuilder sb = new StringBuilder();
        for(int i = 1; i < n+1; i++){
            if(i == start) sb.append("- "); // 목적지가 자신이면 "-" 출력
            else{ // 목적지가 다른 곳이면 parents에서 탐색
                int current = i;
                while(parents.get(current) != start){
                    current = parents.get(current);
                }
                sb.append(current + " ");
            }
        }
        System.out.println(sb);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        answer = new int[n+1][n+1];
        graph = new ArrayList[n+1];
        for(int i = 0; i < n+1; i++)
            graph[i] = new ArrayList<>();

        for(int i = 0; i < m; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            graph[a].add(new Edge(b, cost));
            graph[b].add(new Edge(a, cost));
        }

        for(int i = 1; i < n+1; i++){
            dijkstra(i);
        }
    }

    static class Edge{
        int vertex, cost;
        public Edge(int vertex, int cost){
            this.vertex = vertex;
            this.cost = cost;
        }
    }
}