[백준] 1916번 - 최소비용 구하기 (Java)

풀이

키워드

• 다익스트라(Dijkstra)

  일반적인 다익스트라 알고리즘으로 풀리는 문제이다. 한 노드에서 각 노드까지 갈 수 있는 최단거리를 구해야 하며, 각 노드마다 가중치가 각각 다르므로 DFS, BFS로는 풀 수 없고 다익스트라로 풀어야 한다는 것을 알 수 있다.

 

  우선순위 큐(PriorityQueue)를 사용해서 풀면 훨씬 빠르고 편리하다. 우선순위 큐를 사용하면 현재 큐를 최적의 방법으로 정렬하여 가장 거리가 짧은 노드부터 검사할 수 있게 해주며, 이 때문에 각 노드의 방문여부를 체크할 필요가 사라진다. 

 

  푸는 방식을 간단하게 소개하면 다음과 같다.

1. 도시들의 그래프인 arr[]이 있고, 시작점에서 각 도시까지의 거리를 나타낸 dist[]가 있다.
2. dist[]는 시작점은 0으로, 나머지는 Inf 값으로 설정해준다.
3. 이후, 시작점에서 연결된 노드들을 탐색하며, 지금까지의 비용(0)과 연결된 도시까지 소요되는 비용의 합이 dist[다음도시] 보다 적다면, dist[다음도시]를 이 비용의 합으로 갱신해주고 우선순위 큐에 현재 상황을 넣어준다.(다음도시번호, 도시까지 소요된 비용의 합)
4. 그 다음으로는 가장 비용이 적은 도시를 방문하여, 그 도시에서 3번과 같은 방식으로 탐색을 시도할 것이다.
5. 이를 우선순위 큐가 비어질 때까지 반복한다.

 

  다만 주의해야 할 점 한 가지는, 두 도시간의 경로가 두 개 이상 있을 수도 있다는 것이다. 예를 들어, A -> B로 가는 경로가 가중치가 10인 경로와 20인 경로가 있을 수도 있다. 따라서 도시들이 연결된 그래프를 단순히 2차원 배열로 표현하는 것은 옳지 않다. (물론 방법이 있을 수는 있겠지만, 복잡해진다.) 그래서 나는 ArrayList를 배열로 해서 해결했다.

 

---

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.PriorityQueue;
import java.util.Arrays;
import java.util.ArrayList;


public class Main {
	static int N, M, S, E;
	static ArrayList<City>[] arr;
	static int [] dist;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		dist = new int[N+1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		arr = new ArrayList[N+1];
		for(int i = 1; i < N+1; i++) {
			arr[i] = new ArrayList<City>();
		}
		M = Integer.parseInt(br.readLine());
		
		String [] inputs;
		for (int i = 0; i < M; i++) {
			inputs = br.readLine().split(" ");
			int start = Integer.parseInt(inputs[0]);
			int end = Integer.parseInt(inputs[1]);
			int cost = Integer.parseInt(inputs[2]);
			arr[start].add(new City(end, cost));
		}
		inputs = br.readLine().split(" ");
		S = Integer.parseInt(inputs[0]);
		E = Integer.parseInt(inputs[1]);
		
		dijkstra();
		
		System.out.print(dist[E]);
	}
	
	public static void dijkstra() {
		PriorityQueue<City> pq = new PriorityQueue<City>();
		dist[S] = 0;
		pq.offer(new City(S, 0));
		
		while(!pq.isEmpty()) {
			City cur = pq.poll();
			
			for (City next : arr[cur.num]) {
				int nextDist = next.cost + cur.cost;
				if (nextDist < dist[next.num]) {
					dist[next.num] = nextDist;
					pq.offer(new City(next.num, nextDist));
				}
			}
		}
	}
	
	static class City implements Comparable<City> {
		int num;
		int cost;
		
		public City(int num, int cost) {
			this.num = num;
			this.cost = cost;
		}
		
		@Override
		public int compareTo(City next) {
			return this.cost - next.cost;
		}
	}
}

 

---

출처 : www.acmicpc.net/problem/1916

1916번: 최소비용 구하기