문제 링크
https://www.acmicpc.net/problem/1916
문제
N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째 도시에서 B번째 도시까지 가는데 드는 최소비용을 출력하여라. 도시의 번호는 1부터 N까지이다.
입력
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다.
그리고 M+3째 줄에는 우리가 구하고자 하는 구간 출발점의 도시번호와 도착점의 도시번호가 주어진다. 출발점에서 도착점을 갈 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 출발 도시에서 도착 도시까지 가는데 드는 최소 비용을 출력한다.
5
8
1 2 2
1 3 3
1 4 1
1 5 10
2 4 2
3 4 1
3 5 1
4 5 3
1 5
풀이
가중치가 존재하는 그래프에서의 노드간의 최단 거리를 구하는 문제이기 때문에 다익스트라(Dijkstra) 알고리즘을 이용하여 풀었다.
먼저 Node(여기서는 도시) 객체를 생성하기 위해서 노드 클래스를 정의해야 한다. 노드 클래스를 통해 노드 객체를 생성한 뒤 우선순위 큐(PriorityQueue)에서 노드를 비교해야 한다.
class Node implements Comparable<Node> { // 노드를 우선순위 큐에 넣기 위해 Comparable 인터페이스를 구현해야 한다.
int end; // 노드의 목적지
int weight; // 노드의 가중치(여기서는 버스 비용)
Node(int end, int weight) {
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Node o) { // 가중치를 기준으로 오름차순 정렬()
return weight - o.weight;
}
}
Node 클래스를 만들고 객체의 정렬 순서를 정의하는 데 사용하는 인터페이스인 Comparable<>를 implements해야 한다. 이후 생성자를 만들어 목적지(end)와 비용(weight)를 노드 객체에 할당한 후 compareTo() 메서드를 오버라이딩하여 Node 객체를 가중치를 기준으로 오름차순 정렬하여 우선순위 큐에서 올바른 순서를 유지하는 데 이 메서드가 필요하다.
compareTo() 메서드는 PriorityQueue와 같은 자료구조에서 노드를 정렬하는 데 사용된다. PriorityQueue는 기본적으로 최소 힙(min-heap) 구조를 가지므로, weight가 가장 작은 노드가 가장 먼저 나오게 된다.
다익스트라의 기본적인 동작 원리는 다음과 같다.
-
출발 노드를 지정한다.
-
출발 노드에서 각 노드까지의 최단 거리를 저장하는 테이블(배열)을 초기화한다.
출발 노드에서 자기 자신까지의 거리는 0으로, 다른 모든 노드까지의 거리는 무한대(혹은 충분히 큰 값)로 설정한다. -
방문하지 않은 노드 중에서 출발 노드와의 거리가 가장 짧은 노드를 선택한다.
-
해당 노드를 방문한 것으로 표시하고(방문처리된 노드의 최단 거리는 갱신하지 않는다), 그 노드를 경유로 해서 다른 노드로 가는 최단 거리를 계산하여 갱신한다.
이 때, 출발 노드를 경유하여 가는 거리와 현재 최단 거리를 비교하여 둘 중 더 짧은 거리를 최단 거리로 갱신하여 저장한다. -
모든 노드를 방문할 때까지 3과 4를 반복한다.
다음은 다익스트라의 동작 원리를 통해서 문제를 해결한 전체 코드이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
class Node implements Comparable<Node> { // 노드를 우선순위 큐에 넣기 위해 Comparable 인터페이스를 구현해야 한다.
int end; // 노드의 목적지
int weight; // 노드의 가중치(여기서는 cost)
Node(int end, int weight) {
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Node o) { // 가중치를 기준으로 오름차순 정렬()
return weight - o.weight;
}
}
public class Main {
static int N, M; // N: 노드(도시)의 개수, M: 엣지(버스 노선)의 개수
static ArrayList<ArrayList<Node>> list; // 노드(도시)간의 인접 리스트
static int[] dist; // 출발지점부터 노드(도시)간의 거리 배열
static boolean[] visited; // 방문 여부 배열
static final int INF = Integer.MAX_VALUE; // 무한대
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine()); // 노드(도시)의 개수
M = Integer.parseInt(br.readLine()); // 엣지(버스 노선)의 개수
list = new ArrayList<>(); // 노드(도시)간의 인접 리스트
for (int i = 0; i <= N; i++) {
list.add(new ArrayList<>()); // 노드(도시)간의 인접 리스트 초기화하여 이중 리스트 형태로 만든다.
}
dist = new int[N + 1]; // 출발지점부터 노드(도시)간의 거리 배열
Arrays.fill(dist, INF); // 거리 배열을 무한대로 초기화
visited = new boolean[N + 1]; // 방문 여부 배열
for (int i = 0; i < M; i++) {
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int start = Integer.parseInt(st.nextToken()); // 해당 노드의 출발지점
int end = Integer.parseInt(st.nextToken()); // 해당 노드의 도착지점
int weight = Integer.parseInt(st.nextToken()); // 해당 노드의 가중치(비용)
list.get(start).add(new Node(end, weight)); // 출발지점을 기준으로 도착지점과 가중치를 인접 리스트에 추가
}
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int startPos = Integer.parseInt(st.nextToken()); // 이 문제에서의 출발 노드(도시)
int endPos = Integer.parseInt(st.nextToken()); // 이 문제에서의 최종 도착 노드(도시)
sb.append(dijkstra(startPos, endPos)); // 다익스트라 알고리즘으로 출발지점부터 최종 도착지점까지의 최소 비용을 구한다.
System.out.println(sb);
}
public static int dijkstra(int start, int end) { // 다익스트라 알고리즘
PriorityQueue<Node> pq = new PriorityQueue<>(); // 우선순위 큐를 이용하여 가중치가 낮은 노드부터 방문하도록 한다.
pq.offer(new Node(start, 0)); // 출발지점인 1을 우선순위 큐에 넣는다.
dist[start] = 0; // 출발지점부터 출발지점까지의 거리는 0이다.
while (!pq.isEmpty()) { // 우선순위 큐가 빌 때까지 반복한다.
Node currentNode = pq.poll(); // 우선순위 큐에서 현재 가장 가까운(가중치가 작은) 노드를 하나씩 꺼낸다.
int current = currentNode.end; // 꺼내온 노드로 이동한다.
if (!visited[current]) { // 방문하지 않은 노드라면
visited[current] = true; // 방문 여부 완료 처리
for (Node node : list.get(current)) { // 현재 노드와 연결된 노드들을 확인한다.
if (!visited[node.end] && dist[node.end] > dist[current] + node.weight) { // 방문하지 않은 노드이고, 현재 노드를 거쳐서 가는 것이 더 가깝다면
dist[node.end] = dist[current] + node.weight; // 해당 노드의 최소 비용을 갱신한다.
pq.offer(new Node(node.end, dist[node.end])); // 해당 노드를 우선순위 큐에 넣는다.
}
}
}
}
return dist[end]; // 최종 도착지점까지의 최소 비용을 반환한다.
}
}
참고 사이트: https://steady-coding.tistory.com/84
