[백준]1916: 최소비용 구하기 - JAVA

[백준]1916: 최소비용 구하기

www.acmicpc.net/problem/1916

풀이

 

전형적인 다익스트라 알고리즘을 사용하는 문제였다. 

 

채점할때 50퍼센트에서 계속 틀리길래 이것 저것 건드려 보다가 초기화 하는 값을 변경해 주었더니 맞았다. 거리를 계산하는 문제들을 풀 때에는 초기화 값을 항상 신경써서 설정해 주어야 겠다.

 

코드

import java.util.*;
 
public class Main {    
    
    static int[][] node;
    static int[][] bus;
    static int n, m, start, end;
    static int[] dist;
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        n = scan.nextInt();
        node = new int[n + 1][n + 1];
        
        m = scan.nextInt();
        bus = new int[m][3];
        for(int i = 0; i < m; i++) {
            bus[i][0] = scan.nextInt();
            bus[i][1] = scan.nextInt();
            bus[i][2] = scan.nextInt();
        }
        
        start = scan.nextInt(); //시작노드
        end = scan.nextInt(); //도착노드
        dist = new int[n + 1]; //start로부터 각 노드까지 최단거리 계산
        
        //값 초기화
        for(int i = 1; i <= n; i++) {
            dist[i] = 1000000001; //최대 도시의 개수 1000 * 간선의 최대 비용 1000000  + 1 값이 최대값이 된다.
            for(int j = 1; j <= n; j++) {
                node[i][j] = 1000000001;
            }
        }
        
        for(int i = 0; i < m; i++) {
            int x = bus[i][0];
            int y = bus[i][1];
            int value = bus[i][2];
            if(node[x][y] > value) { //더 작은 가중치 값으로 갱신
                node[x][y] = value;
            }
        }
        
        dijkstra();
        System.out.println(dist[end]);
    }    
    
    public static void dijkstra() {
        PriorityQueue<Integer> q = new PriorityQueue<>(); //최소 힙 사용하여 구현
        q.offer(start);
        dist[start] = 0;
        
        while(!q.isEmpty()) {
            int current = q.poll();
            
            for(int i = 1; i <= n; i++) {
                //자기 자신으로 가는 경우를 제외하고, 현재 노드에서 i로 가는 가중치가 더 작은 값이 있다면 갱신해 준다.
                if(i != current && dist[i] > dist[current] + node[current][i]) {
                    dist[i] = dist[current] + node[current][i];
                    q.offer(i); //해당 노드를 우선순위 큐에 담아서 더 작은 값부터 탐색하도록 한다. 
                }
            }
        }
    }
}