백준 11779 - 최소비용 구하기2

Java

11779 번 - 최소비용 구하기 2

문제

접근 방법

이전 문제에서, 시작 도시에서 도착 도시까지 경유한 도시들과 그 총 도시의 개수를 구하는 것이 추가 된 문제이다.

다익스트라를 계산할 때, 새로운 경유 도시를 거쳐 더 짧은 비용으로 도착 도시를 갈 수 있으면,

1. 기존의 도착 루트를 초기화한 뒤
2. 경유하는 도시까지 도달한 루트 정보로 수정하고
3. 경유 도시를 넣어 새로운 루트로 갱신한다.

코드

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;
    	// 최소  비용 구하기 2 초기화 시작
    	List<List<Integer>> route = new ArrayList<>();
    	
    	for(int i = 0; i <= n; i++) {
    		route.add(new ArrayList<>());
    	}
    	
    	// ---------- 초기화 끝 -----------
		// 다익스트라
    	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];
    				
    				// 도착 루트를 초기화한다.
    				route.get(i).clear();
    				// 경유하는 도시까지 도달한 루트 정보를 도착 루트에 넣는다.
    				for(int c : route.get(curN))
    					route.get(i).add(c);
    				// 경유 도시도 루트에 추가하여, 시작 점에서 해당 도시까지의 루트를 갱신한다.
    				route.get(i).add(curN);
    			}
    		}
    	}
    	// 결과 출력
    	route.get(endCity).add(endCity);
    	System.out.println(city[endCity]);
    	System.out.println(route.get(endCity).size());
    	for(int c : route.get(endCity)) {
    		System.out.print(c);
    		System.out.print(" ");
    	}
    	br.close();
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

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

개선할 점