문제

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

Gold V

코드 (Java)

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

public class Main {

    private static int[][] graph;
    private static int[] least_costs;
    private static boolean[] visited;
    private static int N;

    private static class Node implements Comparable<Node> {
        private final int end, cost;

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

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.cost, o.cost);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(bf.readLine());
        int M = Integer.parseInt(bf.readLine());

        //setup for edges
        graph = new int[N+1][N+1];
        least_costs = new int[N+1];
        visited = new boolean[N+1];
        for (int i = 1; i <= N; ++i) {
            least_costs[i] = Integer.MAX_VALUE;
            for (int j = 1; j <= N; ++j) {
                graph[i][j] = -1;
            }
        }

        StringTokenizer st;

        for (int i = 0; i < M; ++i) {
            st = new StringTokenizer(bf.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            if (graph[start][end] == -1 || cost < graph[start][end]) {
                graph[start][end] = cost;
            }
        }

        st = new StringTokenizer(bf.readLine(), " ");
        int start_city = Integer.parseInt(st.nextToken());
        int dst_city = Integer.parseInt(st.nextToken());

        dijkstra(start_city);

        System.out.print(least_costs[dst_city]);
    }

    private static void dijkstra(int start_city) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(start_city, 0));
        least_costs[start_city] = 0;

        //dijkstra
        while (!q.isEmpty()) {
            int next_city = q.poll().end;
            if (!visited[next_city]) {
                visited[next_city] = true;
                for (int i = 1; i <= N; ++i) {
                    if (graph[next_city][i] != -1) {
                        int cost = least_costs[next_city] + graph[next_city][i];
                        if (cost < least_costs[i]) {
                            least_costs[i] = cost;
                            q.add(new Node(i, cost));
                        }
                    }
                }
            }
        }
    }
}

풀이

그냥 dijkstra algorithm 구현이다. 다만 좀 오래 걸렸는데 이유는...

1. dijkstra를 너무 오랜만에 구현해서(...)
   이 링크를 보고 복습했다. 예전에 C로 구현을 했을 때 직접 minheap를 만들어가지고(...) 세부적으로 구현했었는데 이번에는 중간에 최소비용이 변동된채로 추가하고 싶어도 이를 즉각 수정하는 것이 API상 불가능하기 때문에 그냥 priority queue에 넣는 형태로 구현을 함. 메모리가 좀 낭비되지만, semantic 적으로 크게 문제는 되지 않는다.

2. Read/WriteBuffer이랑 StringTokenizer쓰느라 좀 오래 걸렸다. 그래도 이제는 다 이해되는 상황.

다시보니 1번의 이유가 가장 컸던것 같다.

위는 adjacency matrix를 썼지만, 처음에 구상한 방식은 위와 같지 않았으며 이는 밑부분 참고. 이것도 정답인 답이며, LinkedList랑 ArrayList를 활용했다. 메모리랑 시간이 앞의 것보다 좀 더 많이 잡아먹는다.

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

public class Main {

    private static ArrayList<LinkedList<Node>> edges;
    private static int[] least_costs;
    private static boolean[] visited;
    private static int N;

    private static class Node implements Comparable<Node> {
        private final int end, cost;

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

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.cost, o.cost);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(bf.readLine());
        int M = Integer.parseInt(bf.readLine());

        //setup for edges
        edges = new ArrayList<>(N+1);
        least_costs = new int[N+1];
        visited = new boolean[N+1];
        edges.add(null);
        for (int i = 1; i <= N; ++i) {
            least_costs[i] = Integer.MAX_VALUE;
            edges.add(i, new LinkedList<>());
        }

        StringTokenizer st;

        for (int i = 0; i < M; ++i) {
            st = new StringTokenizer(bf.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            edges.get(start).add(new Node(end, cost));
        }

        st = new StringTokenizer(bf.readLine(), " ");
        int start_city = Integer.parseInt(st.nextToken());
        int dst_city = Integer.parseInt(st.nextToken());

        dijkstra(start_city);

        System.out.print(least_costs[dst_city]);
    }

    private static void dijkstra(int start_city) {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(start_city, 0));
        least_costs[start_city] = 0;

        //dijkstra
        while (!q.isEmpty()) {
            int next_city = q.poll().end;
            if (!visited[next_city]) {
                visited[next_city] = true;
                for (Node edge : edges.get(next_city)) {
                     int cost = least_costs[next_city] + edge.cost;
                     if (cost < least_costs[edge.end]) {
                         least_costs[edge.end] = cost;
                         q.add(new Node(edge.end, cost));
                     }
                }
            }
        }
    }
}