백준 1916 - 최소비용 구하기

Java

1916 번 - 최소비용 구하기

문제

접근 방법

일반적인 다익스트라 문제지만, 놓친 부분이 있어 고민을 하였다.

문제에서 “한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다.”라고 주어졌는데, 이 한 도시에서 다른 도시까지 여러개의 버스가 있다는 사실을 간과하고 있었다.

따라서, 여러 간선 중 최소 값만 그래프에 저장하며 해결하였다.

코드

import java.util.*;
import java.io.*;

public class Main {
	static int n, m, result;
	static int MAX_VALUE = 987654321;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	n = stoi(br.readLine());
    	m = stoi(br.readLine());
    	StringTokenizer stk;
		// ---------- 초기화 시작 -----------
    	int[][] bus = new int[n + 1][n + 1];
    	
    	for(int i = 1; i <= n; i++)
    		Arrays.fill(bus[i], 100001);
    	
    	int a,b,v;
    	for(int i = 0; i < m; i++) {
    		stk = new StringTokenizer(br.readLine());
    		
    		a = stoi(stk.nextToken());
    		b = stoi(stk.nextToken());
    		v = stoi(stk.nextToken());
    		
    		// A -> B 도시까지 가는 버스가 하나가 아닐 수 있다.
    		if(v < bus[a][b])
    			bus[a][b] = v;
    	}
    	
    	int startCity, endCity;
    	
    	stk = new StringTokenizer(br.readLine());
    	startCity = stoi(stk.nextToken());
    	endCity = stoi(stk.nextToken());
    	
    	int[] city = new int[n + 1];
    	boolean[] vis = new boolean[n + 1];
    	Arrays.fill(city, MAX_VALUE);
    	city[startCity] = 0;
    	// ---------- 초기화 끝 -----------
		// 다익스트라
    	int min;
    	int curN = -1;
    	while(true) {
    		min = MAX_VALUE;
    		for(int i = 1; i <= n; i++) {
    			if(!vis[i] && city[i] < min) {
    				min = city[i];
    				curN = i;
    			}
    		}
    		
    		if(min == MAX_VALUE)
    			break;
    		
    		vis[curN] = true;
    		
    		for(int i = 1; i <= n; i++) {
    			if(!vis[i] && bus[curN][i] != 100001 && city[i] > city[curN] + bus[curN][i]) {
    				city[i] = city[curN] + bus[curN][i];
    			}
    		}
    	}
    	// 결과 출력
    	System.out.println(city[endCity]);
    	br.close();
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

그래프 문제일 경우 A → B로 가는 간선이 하나가 아닐 수 있다.

개선할 점