[백준 1916번 / Java] 최소비용 구하기 / 다익스트라(Dijkstra)

문제 링크

Gold 5

 

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

1916번: 최소비용 구하기

 

 

 

 

 

첫 풀이

단순 BFS로 구해보려했던 것 같다.

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

public class Main {

    private static int N;
    private static int M;
    private static int[][] arr;
    private static int start;
    private static int end;
    private static List<Integer> answer = new ArrayList<>();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        arr = new int[M][3];

        StringTokenizer st;

        for(int i = 0; i < M; i ++) {
            st = new StringTokenizer(br.readLine(), " ");

            for(int j = 0; j < 3; j ++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        st = new StringTokenizer(br.readLine(), " ");
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        Queue<int []> queue = new LinkedList<>();
        queue.add(new int[]{start, 0});

        bfs(queue);

        Collections.sort(answer);

        System.out.println(answer.get(0));

    }

    private static void bfs(Queue<int[]> queue) {
        while(!queue.isEmpty()) {
            int size = queue.size();

            for(int i = 0; i < size; i ++) {
                int[] tmp = queue.poll();
                int current = tmp[0];
                int cost = tmp[1];

                if(current == end) {
                    answer.add(cost);
                    continue;
                }

                for(int j = 0; j < M; j ++) {
                    if(arr[j][0] == current) {
                        queue.add(new int[] {arr[j][1], cost + arr[j][2]});
                    }
                }
            }
        }
    }
}

 

버스의 대수가 최대 10만대라는 조건이 있었으므로 당연히 시간초과가 발생했다.

 

 

 

두번째 풀이

최단거리 경로를 구할 때 활용하는 DP의 대표적인 최단 경로 탐색 알고리즘인 다익스트라(Dijkstra)를 활용했다.

 

다익스트라 알고리즘에 대한 자세한 설명은 아래 포스팅을 참고하기 바란다.

https://mag1c.tistory.com/452

 

bfs와의 차이는 아무래도, 현재 방문하고있는 노드에 대한 체크를 해주지 못해서 시간초과가 발생한 것 같다.

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

public class Main {

    private static int N;
    private static int M;
    private static int start;
    private static int end;
    private static int[] dist;
    private static boolean[] visited;
    private static List<List<Node>> nodeList = new ArrayList<>();

    static class Node implements Comparable<Node> {
        int node;
        int cost;

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

        @Override
        public int compareTo(Node o) {
            return cost - o.cost;
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
        StringTokenizer st;

        for(int i = 0; i <= N; i ++) {
            nodeList.add(new ArrayList<>());
        }

        for(int i = 0; i < M; i ++) {
            st = new StringTokenizer(br.readLine(), " ");
            int before = Integer.parseInt(st.nextToken());
            int after = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            nodeList.get(before).add(new Node(after, weight));
        }

        st = new StringTokenizer(br.readLine(), " ");
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());

        dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
        visited = new boolean[N + 1];

        System.out.println(dist());
    }

    private static int dist() {
        PriorityQueue<Node> nodeQueue = new PriorityQueue<>();
        nodeQueue.offer(new Node(start, 0));

        while (!nodeQueue.isEmpty()) {
            Node curNode = nodeQueue.poll();
            int cur = curNode.node;

            if(!visited[cur]) {
                visited[cur] = true;

                for(Node node : nodeList.get(cur)) {
                    if(!visited[node.node] && dist[node.node] > dist[cur] + node.cost) {
                        dist[node.node] = dist[cur] + node.cost;
                        nodeQueue.offer(new Node(node.node, dist[node.node]));
                    }
                }
            }
        }

        return dist[end];
    }
}