[BOJ] 11779 최소비용 구하기2

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

11779번: 최소비용 구하기 2

2022-06-29

---

1) ArrayList 들고 다니면서

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main11779_BufferedReader {
    static class Route implements Comparable<Route>{
        int num;
        int cost;
        List<Integer> bus = new ArrayList<>();
 
        public Route(int num, int cost, List<Integer> bus) {
            this.num = num;
            this.cost = cost;
            this.bus = bus;
        }
 
        @Override
        public int compareTo(Route o) {
            return this.cost - o.cost;
        }
    }
    public static int N, M;
    public static List<List<Route>> list;
    public static List<Integer> answer;
    public static PriorityQueue<Route> pq;
    public static int[] dist;
    public static void solve(int start, int end) {
        pq = new PriorityQueue<>();
        pq.add(new Route(start, 0, answer));
        dist[start] = 0;
        boolean[] vtd = new boolean[N+1];
        while(!pq.isEmpty()) {
            Route r = pq.poll();
 
            if(vtd[r.num]) continue;
            vtd[r.num] = true;
 
            for(Route ro: list.get(r.num)) {
                if(dist[ro.num] > dist[r.num] + ro.cost) {
                    dist[ro.num] = dist[r.num] + ro.cost;
                    List<Integer> tmp = new ArrayList<>(r.bus);
                    tmp.add(ro.num);
                    if(ro.num == end) {
                        answer = tmp;
                    }
                    pq.add(new Route(ro.num, dist[ro.num], tmp));
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(bf.readLine());
        M = Integer.parseInt(st.nextToken());
 
        list = new ArrayList<>();
        dist = new int[N+1];
        for(int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
            dist[i] = 987654321;
        }
 
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(bf.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list.get(a).add(new Route(b, c, new ArrayList<>()));
        }
 
        st = new StringTokenizer(bf.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
 
        answer = new ArrayList<>();
        answer.add(start);
 
        solve(start, end);
 
        System.out.println(dist[end]);
        System.out.println(answer.size());
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < answer.size(); i++)  sb.append(answer.get(i)).append(" ");
        System.out.println(sb.toString());
    }
}

 

 

2) Visited 경로

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
 
public class Main11779_BufferedReader_visited {
    static class Route implements Comparable<Route>{
        int num;
        int cost;
 
        public Route(int num, int cost) {
            this.num = num;
            this.cost = cost;
        }
 
        @Override
        public int compareTo(Route o) {
            return this.cost - o.cost;
        }
    }
    public static int N, M;
    public static List<List<Route>> list;
    public static PriorityQueue<Route> pq;
    public static int[] dist, visited;
    public static void solve(int start, int end) {
        pq = new PriorityQueue<>();
        pq.offer(new Route(start, 0));
        dist[start] = 0;
        boolean[] vtd = new boolean[N+1];
        while(!pq.isEmpty()) {
            Route r = pq.poll();
 
            if(vtd[r.num]) continue;
            vtd[r.num] = true;
            for(Route ro: list.get(r.num)) {
                if(dist[ro.num] > dist[r.num] + ro.cost) {
                    dist[ro.num] = dist[r.num] + ro.cost;
                    pq.offer(new Route(ro.num, dist[ro.num]));
                    visited[ro.num]  = r.num; // visited[cur] = previous
                }
            }
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(bf.readLine());
        M = Integer.parseInt(st.nextToken());
 
        list = new ArrayList<>();
        dist = new int[N+1];
        visited = new int[N+1];
        for(int i = 0; i <= N; i++) {
            list.add(new ArrayList<>());
            dist[i] = 987654321;
        }
 
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(bf.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            list.get(a).add(new Route(b, c));
        }
 
        st = new StringTokenizer(bf.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());
 
 
        solve(start, end);
 
        List<Integer> temp = new ArrayList<>();
        int find = end;
        while(find > 0) {
            temp.add(find);
            find = visited[find]; //5 -> 4 -> 1
        }
 
        System.out.println(dist[end]);
        System.out.println(temp.size());
        StringBuilder sb = new StringBuilder();
        for(int i = temp.size() - 1; i >= 0; i--) sb.append(temp.get(i)).append(" ");
        System.out.println(sb.toString());
    }
}

#문제풀이

다익스트라 문제이다. 

 

arraylist를 들고다니면서 체크하는 방식으로 풀었는데, 다른 사람들 풀이를 보니 경로를 저장한 방법을 사용한 사람들이 있어서 해당 방법으로도 풀어보았다.

 

예를 들어 1 -> 4 -> 5 라는 경로로 이동 했다고 치면, end(5)부터 경로를 거꾸로 가보면 이런식으로 루트를 찾을 수 있다.

 

visited[5]

             ㄴ visited[4]

                               ㄴ visited[1]