백준 1753) 최단경로 Java 풀이

코드에 문제가 있거나 해석에 오류가 있는 부분 지적해주시면 감사하겠습니다.

 

오랜만에 글을 쓰게 되었는데,,, 자잘자잘한 개인사는 뒤로하고 바로 문제 풀이를 해보겠다. 

이번 문제는 백준 1753번 문제이고 [최단 경로] 이다. 문제 제목을 보면 유추 할 수 있듯이 Djikstra 알고리즘을 적용하여 푸는 문제이다. 

 

 

 

문제를 쭉 읽어보면 첫 번째 줄의 입력 값은 정점(이하 노드)의 개수 V, 간선의 개수 E를 적는다. 두 번째 줄의 경우 시작 노드를 적어주고 3번째 줄~ 마지막 줄 까지는 간선의 개수 만큼 (시작 노드, 목표 노드, 비용)이 주어진다. 

 

핵심은 비용이 모두 양수라는 것. 최단 경로를 구하는 문제에서 비용이 모두 0이상이면 다익스트라 알고리즘을 적용하면 된다. 

 

다익스트라 알고리즘은 검색을 해보며 지식을 익혀보자. 예제에 나와 있는 입력 값을 토대로 그림을 그려보자.

그림1

그림2

 

코드를 통해 이해하면 이런식의 모양이 될거다. graph 배열 외 dis 배열을 하나 생성해서 각 노드를 돌면서 최소 비용의 값을 적어주면 된다. 코드를 봐보자.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;

class Edge implements Comparable<Edge>{
    public int vex; // 노드 번호
    public int cost; // 비용

    public Edge(int vex, int cost){
        this.vex = vex;
        this.cost = cost;
    }

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

public class Main {
    private static int[] dis;
    static ArrayList<ArrayList<Edge>> graph;
    static int V,E,K;

    public void solution(int v){
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.offer(new Edge(v, 0));
        dis[v] = 0;

        while (!pq.isEmpty()){
            Edge tmp = pq.poll();
            int now = tmp.vex;
            int nowCost = tmp.cost;
            if (nowCost > dis[now]) continue; 
            // 중요. "노드 비용 > 노드 까지 발생 비용" 이면 굳이 for문을 돌 필요 없다!
            for (Edge ob : graph.get(now)){
                if (dis[ob.vex] > nowCost+ob.cost){
                    dis[ob.vex] = nowCost + ob.cost;
                    pq.offer(new Edge(ob.vex , nowCost + ob.cost));
                }
            }
        }
    }

    public static void main(String[] args){

        Main main= new Main();

        graph = new ArrayList<>();

        Scanner scanner = new Scanner(System.in);
        V = scanner.nextInt(); // 5
        E = scanner.nextInt(); // 6
        K = scanner.nextInt(); // 1

        for (int i = 0 ; i <= V ; i++){
            graph.add(new ArrayList<Edge>());
        }

        dis = new int[V+1];
        Arrays.fill(dis,Integer.MAX_VALUE);

        for (int i = 0 ; i < E ; i++){
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            int w = scanner.nextInt();

            graph.get(u).add(new Edge(v,w));
        }

        main.solution(K);
        for (int i = 1 ; i <= V ; i ++){
            if (dis[i]!= Integer.MAX_VALUE) System.out.println(dis[i]);
            else System.out.println("INF");
        }
    };
}

main에서 그림2와 같은 형태를 만들고, solution 메서드가 중요한데 solution 메서드에서 우선순위 큐를 사용했다. 큐에서 poll 되는 과정은 비용이 최소인 노드가 나오게 된다. 현재까지 소모된 비용+꺼낸 노드의 비용을 합하여 이전에 이미 적힌 비용보다 낮다면, 이를 갱신 해주는 코드이다. 

 

코드를 보며 제대로 이해하고 넘어가자.

 

 

 배운 점: 
우선순위 큐를 사용함으로 시간복잡도가 logN으로 감소하였다. 다익스트라 => 우선순위 큐를 꼭 사용하자!