1916번 최소비용 구하기

골드 5 - 그래프 이론, 최단 경로

소스 코드

문제 링크

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<ArrayList<Node>> roots = new ArrayList<>();
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine()); // N개의 도시
        int M = Integer.parseInt(br.readLine()); // M개의 버스

        visited = new boolean[N + 1];
        for (int i = 0; i <= N; i++) {
            roots.add(new ArrayList<>());
        }

        // 버스 정보 출발 | 도착 | 비용
        StringTokenizer st;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            roots.get(start).add(new Node(end, cost));
        }

        // 목표: 출발 | 도착
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        int answer = BFS(start, end);
        bw.write(answer + "\n");
        bw.flush();
    }

    private static int BFS(int start, int end) {
        PriorityQueue<Node> queue = new PriorityQueue<>();
        queue.add(new Node(start, 0));

        while (!queue.isEmpty()) {
            Node current = queue.poll();

            if (current.end == end) {
                return current.cost;
            }

            visited[current.end] = true;

            for (Node next :roots.get(current.end)) {
                if (!visited[next.end]) {
                    queue.add(new Node(next.end, current.cost + next.cost));
                }
            }
        }

        return -1;
    }

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

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

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

---

풀이 방법

이전에 많이 본 모양의 문제라서 BFS로 풀려고 했다.

그래서 Node 객체를 만들고 도착 도시와 비용을 받을 수 있게 만들었다. ArrayList를 이중으로 사용해서 출발 도시에서 여러개의 도시로 갈 수 있도록 List를 설정.

그리고는.... 항상 하는 것 처럼 BFS를 돌렸다.

---

나의 첫 제출

import java.io.*;
import java.util.*;

public class Main {
    static ArrayList<ArrayList<Node>> roots = new ArrayList<>();
    static ArrayList<Integer> answer = new ArrayList<>();
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine()); // N개의 도시
        int M = Integer.parseInt(br.readLine()); // M개의 버스

        visited = new boolean[N + 1];
        for (int i = 0; i <= N; i++) {
            roots.add(new ArrayList<>());
        }

        // 버스 정보 출발 | 도착 | 비용
        StringTokenizer st;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());

            roots.get(start).add(new Node(end, cost));
        }

        // 목표: 출발 | 도착
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        BFS(start, end);
        answer.sort(null);

        bw.write(answer.get(0) + "\n");
        bw.flush();
    }

    private static void BFS(int start, int end) {
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(new Node(start, 0));

        while (!queue.isEmpty()) {
            Node current = queue.poll();

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

            visited[current.end] = true;

            for (Node next :roots.get(current.end)) {
                if (!visited[next.end]) {
                    queue.add(new Node(next.end, current.cost + next.cost));
                }
            }
        }
    }

    static class Node {
        int end;
        int cost;

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

전체 경우의 수를 구하고 그 경우의 수 중에서 가장 적은 값을 출력하려고 했다.

근데 왜 실패지...??

배열로 BFS를 풀다가 객체(Node)를 사용해서 하다보니 코드를 처음 작성하는데 약간 헷갈리긴 했는데 BFS 코드는 그래도 잘 작성한 것 같다.

모~~~든 경로의 비용을 구해서 sort를 한 다음 첫번째 값을 출력했는데... 흐음..

---

다시 풀이로 돌아와서

결국 이게 잘못된 방법인가 싶어서 풀이를 찾아봤다.

PriorityQueue를 사용해서 비용이 가장 낮은 경로부터 찾아서 바로 최단 경로를 구하는 방법으로 보인다.

이게 뭐 다익스트라 알고리즘? 이라고 하는데 정확하게 어떤건진 모른다...

코드를 살펴보면 Node 객체도 Comparable을 implements 해서 우선순위 큐에 들어갈때 자동으로 값이 비교되서 순서가 정해지는 것 같다.

그 이후에는 poll을 해서 가장 비용이 낮은 것부터 BFS를 돌아서 목표 도착 도시에 도착하는 즉시 해당 루트의 값을 리턴해서 출력!

음... 이게 다른 모든 경로를 파악하지 않아서 확실히 빠르게 값을 구할 수 있을 것 같긴하다.

내 최초 코드는 2% 정도에서 틀렸습니다가 나왔는데 모든 경로를 다 찾아서 뭔가 메모리나 시간이 초과된건가..? 아니면 모든 경로를 찾는 경우에는 뭔가 다른 값이 들어가서 출력값이 달라지는건가...??

여튼!! 다익스트라 알고리즘 이라는 것을 들었(?)고 PriorityQueue 를 사용해서 최단 경로를 빠르게 구하는 방법에 대해 알 수 있어서 좋았다.