[백준]1719: 택배(java)

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

1719번: 택배

문제

명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하는지 결정하지 못했다. 어떤 경로를 거칠지 정해서, 이를 경로표로 정리하는 것이 여러분이 할 일이다.

예시된 그래프에서 굵게 표시된 1, 2, 3, 4, 5, 6은 집하장을 나타낸다. 정점간의 간선은 두 집하장간에 화물 이동이 가능함을 나타내며, 가중치는 이동에 걸리는 시간이다. 이로부터 얻어내야 하는 경로표는 다음과 같다.

경로표는 한 집하장에서 다른 집하장으로 최단경로로 화물을 이동시키기 위해 가장 먼저 거쳐야 하는 집하장을 나타낸 것이다. 예를 들어 4행 5열의 6은 4번 집하장에서 5번 집하장으로 최단 경로를 통해 가기 위해서는 제일 먼저 6번 집하장으로 이동해야 한다는 의미이다.

이와 같은 경로표를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경로가 주어지는데, 두 집하장의 번호와 그 사이를 오가는데 필요한 시간이 순서대로 주어진다. 집하장의 번호들과 경로의 소요시간은 모두 1000이하의 자연수이다.

출력

예시된 것과 같은 형식의 경로표를 출력한다.

예제 입력 1 

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

예제 출력 1 

- 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 -

---

풀이

다익스트라에 대한 설명은 제외하고, 이문제의 핵심적인 풀이라고 생각되는 부분만 풀이하겠습니다.

우선 다익스트라를 통해 우리는 최소 비용 거리를 구할 수 있습니다.

하지만 문제에서는 그 최소 비용 거리를 가는 경로의 두번째 도착지점을 알고싶어 합니다.

다음은 이문제에서 사용한 다익스트라 함수입니다. 우리가 평소에 사용하는 다익스트라 알고리즘에 path라는 배열 하나 추가된 것 입니다.

static void dijkstra(int start) {
    PriorityQueue<Node> q = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
    q.add(new Node(start, 0));
    dist = new int[N+1];
    visited = new boolean[N+1];
    path = new int[N+1];

    for(int i=1; i<=N; i++) {
        dist[i] = Integer.MAX_VALUE;
    }
    path[start] = start;
    dist[start] = 0;

    while (!q.isEmpty()) {
        Node now = q.poll();

        if (visited[now.v]) {
            continue;
        }
        visited[now.v] = true;

        for (Node next : graph[now.v]) {
            if (!visited[next.v] && dist[next.v] > now.cost + next.cost) {
                dist[next.v] = now.cost + next.cost;
                path[next.v] = now.v;
                q.add(new Node(next.v, dist[next.v]));
            }
        }
    }

    for(int i=1; i<=N; i++) {
        if(i==start) ans.append("-");
        else ans.append(dfs(start, i));

        if(i != N) ans.append(" ");
        else if(start != N) ans.append("\n");
    }
}

path를 사용한 역추적 dfs입니다.

public static int dfs(int start, int i) {
    if(path[i] == start) return i;
    return dfs(path[i], start);
}

위 함수의 설명은 아래와 같습니다.

 

전체 코드

package 백준;

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

public class BJ_G3_1719_택배 {
    static class Node{
        int v; //간선
        int cost; //가중치

        public Node(int v, int cost) {
            this.v = v;
            this.cost = cost;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "v=" + v +
                    ", cost=" + cost +
                    '}';
        }
    }
    static int N, M;
    static ArrayList<Node>[] graph;
    static int[] dist, path;
    static boolean[] visited;
    static StringBuilder ans = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        graph = new ArrayList[N+1];
        for(int i=1; i<=N; i++) {
            graph[i] = new ArrayList<>();
        }

        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            graph[s].add(new Node(e, c));
            graph[e].add(new Node(s, c));
        }

        for(int i=1; i<=N; i++) {
            dijkstra(i);
        }
        System.out.println(ans.toString());
    }

    static void dijkstra(int start) {
        PriorityQueue<Node> q = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
        q.add(new Node(start, 0));
        dist = new int[N+1];
        visited = new boolean[N+1];
        path = new int[N+1];

        for(int i=1; i<=N; i++) {
            dist[i] = Integer.MAX_VALUE;
        }
        path[start] = start;
        dist[start] = 0;

        while (!q.isEmpty()) {
            Node now = q.poll();

            if (visited[now.v]) {
                continue;
            }
            visited[now.v] = true;

            for (Node next : graph[now.v]) {
                if (!visited[next.v] && dist[next.v] > now.cost + next.cost) {
                    dist[next.v] = now.cost + next.cost;
                    path[next.v] = now.v;
                    q.add(new Node(next.v, dist[next.v]));
                }
            }
        }

        for(int i=1; i<=N; i++) {
            if(i==start) ans.append("-");
            else ans.append(dfs(start, i));

            if(i != N) ans.append(" ");
            else if(start != N) ans.append("\n");
        }
    }

    public static int dfs(int start, int i) {
        if(path[i] == start) return i;
        return dfs(path[i], start);
    }
}