[BOJ] 백준 1719 택배

출처:  https://www.acmicpc.net/problem/1719

 Input 

6 10

1 2 2

1 3 1

2 4 5

2 5 3

2 6 7

3 4 4

3 5 6

3 6 7

4 6 4

5 6 2

 

 Output 

- 2 3 3 2 2

1 - 1 4 5 5

1 1 - 4 5 6

3 2 3 - 6 6

2 2 3 6 - 6

5 5 3 4 5 -

 

다익스트라(Dijkstra)을 이용해 최단 경로를 구한 후,

다익스트라 (Dijkstra)

경로 추적으로 통해 각 정점별 가장 먼저 방문해야 하는 정점을 구합니다.

다익스트라에서 경로 추적은 최단 경로상에서 해당 정점을 방문하기 위해

직전 노드들을 계속 추적해보면 알 수 있습니다.

trace[a] = b;

최단 경로상에서 정점 [a]로 가기 직전에 방문 정점: [b]

ex) trace[6] = 5 (정점[6] 방문 직전에 정점[5]를 거쳐야 합니다.)

ex) 정점 [1] → 정점 [6] 경로 추적

    trace[6] = 5

    trace[5] = 2

    trace[2] = 1

    ▶ 1 - 2- 5- 6

 

직전 노드를 저장하기 위해서는 다익스트라 과정에서 

거리를 갱신할 때, 방문 정점을 같이 갱신해주는 것입니다.

 

경로 추적할 때는 자기자신은 『-』 표시하고 

다른 정점은 가장 방문해야되는 정점이 저장되도록 코드 작성

---

인접리스트 그래프 + 우선순위 큐

import java.io.*;
import java.util.*;
 
public class Main {
    static final int INF = Integer.MAX_VALUE;
    static int N, M, K;
    static List<List<Node>> adList; // 인접 리스트
    static StringBuilder sb = new StringBuilder();
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine());
 
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        adList = new ArrayList<>();
        // 인덱스를 1부터 하기 위해 임의로 한 개를 넣어둠
        adList.add(new <Node>ArrayList());
        for (int i = 1; i <= N; i++) {
            adList.add(new <Node>ArrayList());
        }
 
        while(M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt((st.nextToken()));
            int v = Integer.parseInt((st.nextToken()));
            int cost = Integer.parseInt((st.nextToken()));
            adList.get(u).add(new Node(v, cost));
            adList.get(v).add(new Node(u, cost));
        }
         
        for(int i=1; i<=N; i++) {
            // 다익스트라 알고리즘
            dijkstra(i);    
        }
 
        // 정답출력
        System.out.println(sb.toString());
    }   
     
    private static void dijkstra(int start) {
        PriorityQueue<Node> pq = new PriorityQueue<>();
        boolean[] visited = new boolean[N+1];
        int[] trace = new int[N+1];
        // dist[] INF로 초기화
        int[] dist = new int[N+1];
        Arrays.fill(dist, INF);
         
        dist[start] = 0; trace[start] = start;
        pq.add(new Node(start, 0));
         
        while(!pq.isEmpty()) {
            Node current =  pq.poll();
            // 재방문 여부 확인
            if(visited[current.ID]) continue;
            visited[current.ID] = true;
            // 연결된 정점들을 확인 
            for(Node next : adList.get(current.ID)) {
                // 효율적인 처리를 위해 최소 거리 비용이 갱신되는 경우만 queue에 넣어줍니다.
                if(dist[next.ID] > dist[current.ID] + next.distance) {
                    // 최소 거리 비용 갱신
                    dist[next.ID] = dist[current.ID] + next.distance;
                    // 해당 정점(next)을 거치기 위해서는 현재 정점(current)을 직전에 거쳐야하는 표시
                    trace[next.ID] = current.ID;
                    pq.add(new Node(next.ID, dist[next.ID]));
                }
            }
        }
         
        // 경로 추적
        tracert(start, trace);
    }
 
    private static void tracert(int start, int[] trace) {
        // start 정점에서 각 정점[v]까지 최단 경로 추적 
        for(int v = 1; v <= N; v++) {
            // 자기 자신인 경우
            if(v == start) {
                sb.append("- ");
                continue;
            }
            int answer = 0;
            for(int j = v; j != start; j = trace[j]) {
                // 가장 먼저 방문해야되는 정점이 되도록 갱신
                answer = j;
            }
            sb.append(answer + " ");
        }
        sb.append("\n");
    }
}
 
 
class Node implements Comparable<Node> {
    int ID;
    int distance;
 
    public Node(int ID, int distance) {
        this.ID = ID;
        this.distance = distance;
    }
 
    @Override
    public int compareTo(Node target) {
        // 작은 거리 비용이 먼저 오도록
        return this.distance - target.distance;
    }
}

 

인접리스트 그래프 + 선형 방식

import java.io.*;
import java.util.*;
 
public class Main {
    static final int INF = Integer.MAX_VALUE;
    static final int UNVISITED = -1;
    static int N, M;
    static List<List<Node>> adList;
    static int[] dist, trace;
    static boolean[] visited;
    static StringBuilder sb = new StringBuilder();
 
    static class Node {
        int ID;
        int distance;
 
        public Node(int ID, int distance) {
            this.ID = ID;
            this.distance = distance;
        }
    }
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
 
        adList = new ArrayList<>();
        // 인덱스를 1부터 하기 위해 임의로 한 개를 넣어둠
        adList.add(new <Node>ArrayList());
        for (int i = 1; i <= N; i++) {
            adList.add(new <Node>ArrayList());
        }
 
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt((st.nextToken()));
            int v = Integer.parseInt((st.nextToken()));
            int cost = Integer.parseInt((st.nextToken()));
            adList.get(u).add(new Node(v, cost));
            adList.get(v).add(new Node(u, cost));
        }
 
        // 다익스트라 알고리즘
        for (int i = 1; i <= N; i++) {
            // 다익스트라 알고리즘
            dijkstra(i);
        }
 
        // 정답출력
        System.out.println(sb.toString());
 
    }
 
    private static void dijkstra(int start) {
        trace = new int[N + 1];
        dist = new int[N + 1];
        visited = new boolean[N + 1];
 
        Arrays.fill(trace, UNVISITED);
        Arrays.fill(dist, INF);
        for (Node edge : adList.get(start)) {
            dist[edge.ID] = edge.distance;
        }
        for (Node edge : adList.get(start)) {
            trace[edge.ID] = start;
        }
 
        dist[start] = 0;
        trace[start] = start;
        visited[start] = true;
 
        for (int i = 1; i <= N - 2; i++) {
            // 방문하지 않은 정점 중 가장 작은 비용의 정점을 찾는다.
            int current = getSmallIndex();
            visited[current] = true;
 
            // 방문하지 않은 정점들 중 연결된 정점의 최단거리 갱신
            for (Node next : adList.get(current)) {
                if (dist[next.ID] > dist[current] + next.distance) {
                    // 최소 거리 비용 갱신
                    dist[next.ID] = dist[current] + next.distance;
                    trace[next.ID] = current;
                }
            }
        }
        // 경로 추적
        tracert(start);
    }
 
    private static int getSmallIndex() {
        int min = INF;
        int idx = 1;
        for (int i = 1; i <= N; i++) {
            // 방문하지 않은 정점 중 가장 작은 비용의 정점을 찾는다.
            if (!visited[i] && dist[i] < min) {
                min = dist[i];
                idx = i;
            }
        }
        return idx;
    }
 
    private static void tracert(int start) {
        // start 정점에서 각 정점[v]까지 최단 경로 추적 
        for(int v = 1; v <= N; v++) {
            // 자기 자신인 경우
            if(v == start) {
                sb.append("- ");
                continue;
            }
            int answer = 0;
            for(int j = v; j != start; j = trace[j]) {
                // 가장 먼저 방문해야되는 정점이 되도록 갱신
                answer = j;
            }
            sb.append(answer + " ");
        }
        sb.append("\n");
    }
 
}