백준 11779 java - 최소비용 구하기 2 (다익스트라)

문제, 입출력, 테스트케이스

해당 문제는 다익스트라 알고리즘 문제이다. 

최소비용 구하기 문제와 다른 점은 최소 비용 갖는 경로와 도시 갯수를 출력하는 것인데 이것은 따로 배열을 만들어서 출력하면 되는 부분이므로 크게 힘든 점은 없었다.

2022.07.15 - [알고리즘공부(AlgorithmStudy)/알고리즘이론(AlgorithmTheory)] - 백준 1916 java - 최소비용 구하기(다익스트라 알고리즘)

 

<문제 풀이/접근과정>
1. 다익스트라를 구현한다.
2. 우선순위 큐에 comparator를 넣는 버전이 아닌 Node 클래스 생성 및 compareTo 메소드 오버라이딩 하는 방식으로 구현 해봄
3. 이전 경로 등록할 배열 생성
4. 다익스트라 알고리즘 실행 후 최소 비용 갖는 경로 및 도시 갯수 구하기
5. 출력

 

 

백준 1916 java - 최소비용 구하기(다익스트라 알고리즘)

package dijkstra;
import java.util.*;
import java.io.*;

public class Boj_11779_최소비용구하기2 {
	static int prv[], dist[];
	static List<int[]>[] v;
	
	static public class Node implements Comparable<Node>{
		int nxt;
		int d;
		public Node(int nxt, int dist) {
			this.nxt = nxt;
			this.d = dist;
		}
		@Override
		public int compareTo(Node o) {
			return this.d - o.d;
		}
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int m = Integer.parseInt(br.readLine());
		v = new ArrayList[n+1];
		PriorityQueue<Node> pq = new PriorityQueue<>();
		dist = new int[n+1];
		prv = new int[n+1];
		for (int i = 1; i <= n; i++) {
			prv[i] = i;
			dist[i] = 200000000;
			v[i] = new ArrayList<int[]>();
		}
		
		StringTokenizer stz;
		
		for (int i = 0; i < m; i++) {
			stz = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(stz.nextToken());
			int to = Integer.parseInt(stz.nextToken());
			int d = Integer.parseInt(stz.nextToken());
			v[from].add(new int[] {to, d});
		}
		stz = new StringTokenizer(br.readLine());
		
		int start = Integer.parseInt(stz.nextToken());
		int end = Integer.parseInt(stz.nextToken());
		
		dist[start] = 0;
		pq.offer(new Node(start, 0));
		
		while(!pq.isEmpty()) {
			Node cur = pq.poll();
			
			if(dist[cur.nxt] != cur.d )continue;
			
			for (int i = 0; i < v[cur.nxt].size(); i++) {
				int nxt[]= v[cur.nxt].get(i);
				
				if(dist[nxt[0]] > cur.d + nxt[1]) {
					dist[nxt[0]] = cur.d + nxt[1];
					prv[nxt[0]] = cur.nxt;
					pq.offer(new Node(nxt[0], dist[nxt[0]]));
				}
			}
		}
		String answer = ""+ end;
		int tmp = end;
		int cnt = 1;
		while(true) {
			tmp = prv[tmp];
			answer = tmp + " " + answer;
			cnt++;
			
			if(start == tmp)break;
		}
		
		System.out.println(dist[end]);
		System.out.println(cnt);
		System.out.print(answer);
	}
}