[Algorithm/Java][백준] 1916번 최소비용 구하기

[BOJ] 1916번 최소비용 구하기

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

문제 접근

양의 가중치를 가진 간선으로 이루어진 그래프에서 최단 경로를 찾는 문제여서 다익스트라와 벨만포드 알고리즘 2개를 모두 적용해서 구현했다.
다익스트라 알고리즘은 우선순위 큐를 이용해서 시간복잡도를 줄였고, 다익스트라와 벨만포드 알고리즘은 포스트에 정리했다.

[알고리즘] 다익스트라 & 벨만포드

Code

다익스트라

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

class Node implements Comparable<Node> {
    int to;
    int cost;

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

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

public class BOJ1916 {
    static int[] distance;
    static ArrayList<ArrayList<Node>> list; // 인접리스트
    static boolean[] visited;
    static int start, end;
    static int n,m;
    public static void main(String[] args) throws IOException {
        initD();
        System.out.println(dijkstra(start, end));
    }

    public static void initD() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        distance = new int[n+1];
        list = new ArrayList<>();
        for(int i = 0; i<=n; i++){
            list.add(i, new ArrayList<>());
        }

        for(int i = 0; i<m; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            list.get(from).add(new Node(to, cost));
        }
        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
    }
    public static int dijkstra(int start, int end){
                // 우선순위 큐를 이용한 다익스트라 알고리즘
        PriorityQueue<Node> pq = new PriorityQueue<>();
                // 최단경로 테이블 초기화
                Arrays.fill(distance, Integer.MAX_VALUE);
        pq.offer(new Node(start, 0));
        visited = new boolean[n + 1];
        distance[start] = 0;
        while(!pq.isEmpty()){
            Node node = pq.poll();
            int cur = node.to;
            if(cur == end) break;
            if(visited[cur]) continue;
            visited[cur] = true;
            for (Node next : list.get(cur)) {
                if(!visited[next.to] && distance[next.to] > distance[cur] + next.cost){
                    distance[next.to] = distance[cur] + next.cost;
                    pq.add(new Node(next.to, distance[next.to]));
                }
            }
        }
        return distance[end];
    }
}

벨만포드

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

class Bus{
    int from;
    int to;
    int cost;
    public Bus(int from, int to, int cost) {
        this.from = from;
        this.to = to;
        this.cost = cost;
    }
}
public class BOJ1916 {
    static Bus[] buses;  // 간선들의 정보를 저장
    static int[] distance;
    static boolean[] visited;
    static int start, end;
    static int n,m;
    public static void main(String[] args) throws IOException {
        initB();
        System.out.println(bellmanFord(start));
    }
    public static void initB() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        m = Integer.parseInt(br.readLine());
        distance = new int[n + 1];
        visited = new boolean[n + 1];
        buses = new Bus[m];
        for(int i = 0; i<m; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            Bus bus = new Bus(from, to, cost);
            buses[i] = bus;
        }
        StringTokenizer st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
    }

    public static int bellmanFord(int start){
                // 최단 경로 테이블 초기화
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[start] = 0;
        for(int i = 1; i<=n; i++){
            for(int j = 0; j<m; j++){
                Bus bus = buses[j];
                if(distance[bus.from] == Integer.MAX_VALUE) continue;
                if(distance[bus.to] > distance[bus.from] + bus.cost){
                    distance[bus.to] = distance[bus.from] + bus.cost;
                }
            }
        }
        return distance[end];
    }
}