백준1916_최소비용 구하기

문제

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

[코드]

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc = new Scanner(System.in);
        int City = sc.nextInt();
        int Bus = sc.nextInt();
        int INF = 100000000;
        int dist[][] = new int[City+1][City+1];
        
        for(int i = 1 ; i <= City; i++){
            for(int j = 1 ; j <= City; j++){
                dist[i][j] = INF; //초기화
                if(i==j)
                    dist[i][j] = 0;
            }
        }
        
        for(int i = 0 ; i < Bus; i++){
            int v1 = sc.nextInt();
            int v2 = sc.nextInt();
            int p = sc.nextInt();
            if(dist[v1][v2] > p)
                dist[v1][v2] = p;
        }
        
        
        int f = sc.nextInt();
        int d = sc.nextInt();
    
 
        for(int i = 1 ; i <= City; i++){
            for(int j = 1; j <= City; j++){
                for(int k = 1 ; k <= City; k++){
                    if(dist[j][k] > dist[j][i] + dist[i][k] && i!=j && j!=k && k!=i)
                        dist[j][k] = dist[j][i] + dist[i][k];
                }
            }
        }
        
        System.out.println(dist[f][d]);
    }
    
    
 
}
 
 

[알고리즘]

최단거리? 앞서 풀었던 문제와 비슷해서, 다른 방법으로 풀어보려했다.

인접행렬을 이용해 풀었는데, 플로이드 워샬 알고리즘으로 풀었다. 그냥 코딩하기가 제일 쉬운것 같아서..

근데 계속해서 틀렸다고 나와서 몇번이나 확인했는데, 

알고보니... 도시를 잇는 버스가 여러개가 있을 수 있는 거 였다.

예를 들면... 1 3 도시를 잇는 버스가 2개 있는데 각각 3, 5 의 비용이라면 dist[1][3] 에는 3 을 집어넣어줘야한다는...

질문 검색을 보다가 알게 된 거다. 사실 그걸 안보고도 당연히 알고있을거라고 생각해서 별다른 말이 없었는지 그건 잘 모르겠지만

생각지 못한 포인트에서 계속 오답을 ㅋㅋㅋ 무튼, 그 글이 아니였다면 풀지 못했을 것 같다 ㅜ_ㅜ