[Java/자바 백준 11779] 최소비용 구하기2

풀이

이 문제 정말 매콤했다...

 

일단은 문제 자체에서 주의해야할게

테스트케이스에서 다른 답도 답이 될 수 있다.

스페셜저지로 나온 문제기 때문에 다른 답도 나올 수 있으며,

테케 자체에서도 답이 1,3,5 이지만

1,4,5 도 똑같이 답이 된다... 

이점을 유의하자.. 이거때문에 시간을 많이 썼다.

 

또 시간 초과 나서 route 배열에 전 idx를 담는 로직으로 바꾸다가,

start idx를 특별한 값(여기선-1)로 초기 안해줘서

시간 음청 썼다 ~

-> int배열이 디폴트가 0이기때문에 출발지라는 걸 인식하기위해 -1로 초기화

 

 

풀이를 시작하면

우선 다익스트라를 사용하는 문제이지만, 경로까지 알아야하므로 한 번 더 생각해줘야한다.

고로 route배열을 만들어서 다익스트라 중 최솟값이 될 때 그 전 도시 인덱스를 담아주었따.

 

그 뒤 end -> start로 다시 찾아갈때, route를 써서 routes에 넣어주었다.

시간을 좀 더 줄이고자 stringbuilder를 사용햇다.

 

끝

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

public class Main {
	static int N, V, E, start, end;
	static int[] distance;
	static boolean[] visited;
	static int[] route;
	static ArrayList<Node>[] adjList;
	static ArrayList<Integer> routes;
	static StringBuilder sb = new StringBuilder();
	static final int INF = Integer.MAX_VALUE;
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		V = Integer.parseInt(br.readLine());
		E = Integer.parseInt(br.readLine());
		adjList = new ArrayList[V];
		distance = new int[V];
		visited = new boolean[V];
		route = new int[V];
		
		Arrays.fill(distance, INF);
		Arrays.fill(route, -1);
		for(int i = 0 ; i < V ;i++) {
			adjList[i] = new ArrayList<Node>();
		}
		
		for(int i = 0 ; i < E ; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken()) - 1;
			int v = Integer.parseInt(st.nextToken()) - 1;
			int w = Integer.parseInt(st.nextToken());
			adjList[u].add(new Node(v, w));
		}
		st = new StringTokenizer(br.readLine());
		start = Integer.parseInt(st.nextToken()) - 1;
		end = Integer.parseInt(st.nextToken()) - 1;
		
		distance[start] = 0;
		route[start] = -1;
		for(int i = 0 ; i < V ; i++) {
			int min = Integer.MAX_VALUE;
			int minVertex = -1;
			for(int j = 0 ; j < V ; j++) {
				if(!visited[j] && distance[j] < min) {
					min = distance[j];
					minVertex = j;
				}
			}
			
			if(minVertex == -1) break;
			visited[minVertex] = true;
			for(Node next : adjList[minVertex]) {
				if(!visited[next.v] && distance[next.v] > min + next.w) {
					
					distance[next.v] = min + next.w;
					route[next.v] = minVertex;
				}
			}
		}
		sb.append(distance[end]).append("\n");
		visited = new boolean[V];
		visited[start] = true;
		routes = new ArrayList<>();
		int now = end;
		while(now != -1) {
			routes.add(now);
			now = route[now];
		}
		sb.append(routes.size()).append("\n");
		
		for(int i = routes.size() - 1 ; i >= 0 ; i--) {
			sb.append(routes.get(i) + 1).append(" ");
		}
		System.out.println(sb);
	}

	private static class Node {
		int v, w;
		public Node(int v, int w) {
			this.v = v;
			this.w = w;
		}
	}
}