Baekjoon Online Judge _ 01916 _ 최소비용 구하기

[ Baekjoon Online Judge _ 01916 _ 최소비용 구하기 ]

문제

n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. 그러면 A번째 도시에서 B번째 도시 까지 가는데 드는 최소비용을 출력하여라.

입력

첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.

그리고 m+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다.

출력

첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.

예제 입력

5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5

예제 출력

4

풀이

그동안 최단거리 문제는 플로이드 워셜 알고리즘을 이용해 풀었었다. (더 쉬워서..)

하지만 플로이드 워셜 알고리즘은 n^3 의 시간복잡도를 가지기 때문에

이번엔 n^2 의 시간복잡도를 가지는 다익스트라 알고리즘으로 풀어보았다.

하지만 빡치게도 자꾸 틀렸습니다 가 뜬다 ㅜㅜ

그러다 질문게시판을 보고 버스의 비용이 여러개 입력되는 경우에 대한 처리도 해주었는데

여전히 틀렸습니다가 뜨네?

왜인지 다시 천천히 생각해봐야겠다.

미네미님 댓글 참고해서 수정했다!!

그래도 런타임 에러가 떠서 뭐가 문제지 했는데

visit 배열의 크기를 n+1 로 해주었어야 하는데 m+1 로 했더라ㅜㅜ

전혀 생각지도 못한 사소한 실수였다

정신 똑바로 차리고 해야지

코드

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        final int INF = 100000000;
        boolean[] visit;  //방문여부체크
        int[] distance;   //최소거리
        int[][] costs;    //버스비용 저장(가중치)
        int n, m, start, end;
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt(); //도시개수
        m = sc.nextInt(); //버스개수
        visit = new boolean[n+1];
        distance = new int[n+1];
        costs = new int[n+1][n+1];
        
        //거리 초기화
        //버스비용 무한대로 초기화(자기자신은 0)
        for(int i = 1; i <= n; i++){
            distance[i] = INF;
            for(int j = 1; j <= n; j++){
                costs[i][j] = (i == j)? 0 : INF;
            }
        }
        
        while(m-- > 0){
            int busStart = sc.nextInt();
            int busEnd = sc.nextInt();
            int busCost = sc.nextInt();
            if(busCost < costs[busStart][busEnd])
                costs[busStart][busEnd] = busCost;
        }
        
        start = sc.nextInt();
        end = sc.nextInt();
        
        //다익스트라 알고리즘
        distance[start] = 0; //시작점초기화
        for(int i = 0; i < n; i++){
            int min = INF+1;
            int index = -1;
            
            for(int j = 1; j <= n; j++){
                if(visit[j] == false && min > distance[j]){
                    min = distance[j];
                    index = j;
                }
            }//end for
            visit[index] = true;
            
            for(int j = 1; j <= n; j++){
                if((j != index) && (distance[j] > distance[index] + costs[index][j])){
                    distance[j] = distance[index] + costs[index][j];
                }
            }
        }//end for
        
        System.out.println(distance[end]);
    }
}