[백준] no11779: 최소비용 구하기2 - 다익스트라

문제

N개의 정점(city)과 M개의 간선(bus)이 주어진다.

각 M개의 간선에는 서로다른 비용(cost)가 주어진다.

주어진 A 정점에서 B 정점으로 가는 최소비용/이동한 정점 수/이동한 정점의 순서를 구하라.

문제링크: https://www.acmicpc.net/problem/11779

---

원리

다익스트라

 

---

나의 코드

1. [실패] 

- 원인 1 : 다익스트라 도중반복문 범위 설정

- 원인 2 : 서로 다른 list에 대한 일괄 add 되어버리는 오류 발생

            for(int i=1 ; i<= city_amount ; i++) { // 원인1 부분. i를 1부터 city_amount와 같을 때까지 반복해야한다 
                if(map[now.city][i]!=null) {
                    ArrayList<Integer> now_list = list;
                    now_list.add(i);  // 왜인지 새로 생성한 ArrayList뿐만아니라 기존 now가 가지고 있는 list에도 값이 추가되어버린다.
                    pq.add(new Node(i, now.cost+map[now.city][i], now_list));
                }
            }

 

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

public class no11779 {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int city_amount, bus_amount, min;
//    private static List<ArrayList<Integer>> map;
    private static Integer[][] map, cost_map;
    private static StringTokenizer st;
    private static List<Integer> via;

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

        city_amount = Integer.parseInt(br.readLine());
        bus_amount = Integer.parseInt(br.readLine());

//        for(int i = 0; i<= city_amount; i++) map.add(new ArrayList<>());
        map = new Integer[city_amount+1][city_amount+1];
        cost_map = new Integer[city_amount+1][city_amount+1];
        for(int i = 0; i< bus_amount; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            map[start][end] = cost;
        }

        st = new StringTokenizer(br.readLine(), " ");
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        // 결과 입력용 변수 초기화
        min = 0;
        via = new ArrayList<>();

        dijkstra(A, B);

        bw.write("" + min + "\n");
        bw.write("" + via.size() + "\n");
        for(Integer city : via) bw.write("" + city + " ");

        bw.close();
    }

    private static void dijkstra (int A, int B) {
        PriorityQueue<Node> pq = new PriorityQueue<>((a,b) -> a.cost - b.cost);
        for(int i = 1 ; i <= city_amount ; i++) {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(i);
            if(map[A][i]!=null) pq.add(new Node(i, map[A][i], list));
        }


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

            if(now.city==B) {
                min = now.cost;
                via = now.list;
                break;
            }

            for(int i=0 ; i< city_amount ; i++) {
                if(map[now.city][i]!=null) {
                    ArrayList<Integer> now_list = now.list;
                    now_list.add(i);
                    pq.add(new Node(i, now.cost+map[now.city][i], now_list));
                }
            }
        }
    }

    private static class Node {
        private int city, cost;
        private  ArrayList<Integer> list;
        public Node (int city, int cost, ArrayList<Integer> list) {
            this.city = city;
            this.cost = cost;
            this.list = list;
        }
    }
}

 

2. [로컬 성공/백준 실패]

- 원인 : 알 수 없음. 다만 해당 코드를 사용할 경우, visited가 없이 과도한 객체 생성으로 인해 비효율적이라 판단.

    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int city_amount, bus_amount, min;
    private static Integer[][] map;
    private static StringTokenizer st;
    private static List<Integer> via;

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

        city_amount = Integer.parseInt(br.readLine());
        bus_amount = Integer.parseInt(br.readLine());

        map = new Integer[city_amount+1][city_amount+1];
        for(int i = 0; i< bus_amount; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            map[start][end] = cost;
        }

        st = new StringTokenizer(br.readLine(), " ");
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        // 결과 입력용 변수 초기화
        min = Integer.MAX_VALUE;
        via = new ArrayList<>();

        dijkstra(A, B);

        bw.write("" + min + "\n");
        bw.write("" + via.size() + "\n");
        for(Integer city : via) bw.write("" + city + " ");

        bw.close();
    }

    private static void dijkstra (int A, int B) {
        PriorityQueue<Node> pq = new PriorityQueue<>((a,b) -> a.cost - b.cost);
        for(int i = 1 ; i <= city_amount ; i++) {
            ArrayList<Integer> list = new ArrayList<>();
            list.add(A);
            list.add(i);
            if(map[A][i]!=null) pq.add(new Node(i, map[A][i], list));
        }


        while(!pq.isEmpty()) {
            Node now = pq.poll();
            ArrayList<Integer> list = now.list;

            if(now.city==B) {
                min = Math.min(min,now.cost);
                via = list;
                break;
            }

            for(int i=1 ; i<= city_amount ; i++) {
                if(map[now.city][i]!=null) {
                    ArrayList<Integer> now_list = new ArrayList<>();
                    now_list.addAll(list);
                    now_list.add(i);
                    pq.add(new Node(i, now.cost+map[now.city][i], now_list));
                }
            }
        }
    }

    private static class Node {
        private int city, cost;
        private  ArrayList<Integer> list;
        public Node (int city, int cost, ArrayList<Integer> list) {
            this.city = city;
            this.cost = cost;
            this.list = list;
        }
    }

---

레퍼런스

참고 링크 : https://moonsbeen.tistory.com/239

import java.util.*;
 
public class Main {
    
    static ArrayList<Node>[] list;
    static int n, m, start, end; 
    static int[] dist;
    static int[] route; // 직전 노드 저장
    static boolean[] visited; 
    
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        m = scan.nextInt();
        
        list = new ArrayList[n + 1];
        for(int i = 1; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        
        for(int i = 0; i < m; i++) {
            int s = scan.nextInt();
            int e = scan.nextInt();
            int c = scan.nextInt();
            list[s].add(new Node(e, c));
        }
        
        start = scan.nextInt();
        end = scan.nextInt();
        
        dist = new int[n + 1];
        route = new int[n + 1];
        Arrays.fill(dist, 1000000001);
        visited = new boolean[n + 1];
        dijkstra();
        
        System.out.println(dist[end]);
        
        ArrayList<Integer> routes = new ArrayList<>();
        int current = end;
        while(current != 0) {
            routes.add(current);
            current = route[current];
        }
        System.out.println(routes.size());
        for(int i = routes.size() - 1; i >= 0; i--) {
            System.out.print(routes.get(i) + " ");
        }
    }
    
    public static void dijkstra() {
        PriorityQueue<Node> q = new PriorityQueue<>();
        q.add(new Node(start, 0));
        dist[start] = 0;
        route[start] = 0;
        
        while(!q.isEmpty()) {
            Node current = q.poll();
            
            if(!visited[current.e]) visited[current.e] = true;
            else continue;
            
            for(int i = 0; i < list[current.e].size(); i++) {
                Node next = list[current.e].get(i);
                if(dist[next.e] > dist[current.e] + next.cost) {
                    dist[next.e] = dist[current.e] + next.cost;
                    q.offer(new Node(next.e, dist[next.e]));
                    route[next.e] = current.e;
                }
            }
        }
    }
    
    public static class Node implements Comparable<Node> {
        int e;
        int cost;
        
        public Node(int e, int cost) {
            this.e = e;
            this.cost = cost;
        }
        
        @Override
        public int compareTo(Node n) {
            return this.cost - n.cost;
        }
    }
}