출처: https://www.acmicpc.net/problem/1753
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하세요. 단, 모든 간선의 가중치는 10 이하의 자연수입니다.
입력 형식
첫째 줄에 두 개의 정수 V와 E가 주어집니다.
V: 정점의 개수 (1 ≤ V ≤ 20,000)
E: 간선의 개수 (1 ≤ E ≤ 300,000)
둘째 줄에 시작 정점의 번호 K가 주어집니다. (1 ≤ K ≤ V)
셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어집니다.
u: 시작 정점
v: 도착 정점
w: 가중치 (w는 10 이하의 자연수)
u와 v는 서로 다름
서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수 있음
출력 형식
첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력합니다.
시작점 자신은 0으로 출력
경로가 존재하지 않는 경우에는 INF를 출력
예제 입력 1
5 6 1 5 1 1 1 2 2 1 3 3 2 3 4 2 4 5 3 4 6
예제 출력 1
0 2 3 7 INF
import java.io.;
import java.util.;
public class Main {
static class Node implements Comparable {
int vertex, weight;
Node(int vertex, int weight) {
this.vertex = vertex;
this.weight = weight;
}
@Override
public int compareTo(Node other) {
return this.weight - other.weight;
}
}
public static int[] dijkstra(int V, int K, ArrayList[] graph) {
// 최단 거리 테이블 초기화
int[] distance = new int[V + 1];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[K] = 0;
PriorityQueue pq = new PriorityQueue<>();
// 시작 노드 정보 우선순위 큐에 삽입
pq.offer(____);
while (!pq.isEmpty()) {
// 가장 최단 거리가 짧은 노드 정보 꺼내기
Node current = pq.poll();
// 현재 노드의 최단 거리가 이미 더 짧은 경우 무시
if (distance[current.vertex] < ____) {
continue;
}
// 현재 노드와 연결된 다른 노드들 확인
for (Node next : graph[current.vertex]) {
int cost = distance[current.vertex] + next.weight;
// 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
if (cost < ____) {
distance[next.vertex] = cost;
pq.offer(new Node(next.vertex, cost));
}
}
}
return distance;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int V = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(br.readLine());
ArrayList[] graph = new ArrayList[V + 1];
for (int i = 1; i <= V; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
graph[u].add(new Node(v, w));
}
int[] result = dijkstra(V, K, graph);
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= V; i++) {
if (result[i] == Integer.MAX_VALUE) {
sb.append("INF\n");
} else {
sb.append(result[i]).append("\n");
}
}
System.out.print(sb);
}
}
빈칸 1 : x
정답: new Node(K, 0)
해설: Node 클래스는 Comparable 인터페이스를 구현하여 weight를 기준으로 노드 간 우선순위를 결정합니다. Node 클래스의 compareTo 메소드는 this.weight - other.weight를 반환하여 weight가 작은 노드가 우선순위 큐에서 먼저 추출되도록 합니다. 시작점의 경우 vertex는 시작 노드 번호 K이고, weight는 시작점까지의 거리인 0으로 설정됩니다.
->나는 new Node(0, K)으로 골랐다. 시작점이라길래 0부터 시작하는 줄알았으나 시작 노드 번호가 K라는 것. 문제를 꼼꼼하게 잘 읽기
빈칸 2: x
정답: current.weight
해설: 현재 노드까지의 최단 거리(distance[current.vertex])와 현재까지 계산된 거리(current.weight)를 비교합니다. 이미 저장된 최단 거리가 더 작다면 해당 노드는 이미 처리된 것이므로 무시합니다.
->나는0 으로 골랐다. 최단 거리라고 생각한건지 몰라도 0이 들어가야 한다 생각함. PriorityQueue pq = new PriorityQueue<>();에 Node 객체값이 들어가야 하는데 int 0이 들어간다면 에러가 난다.
빈칸 3: X
정답: distance[next.vertex]
해설: 현재 계산한 비용(cost)과 기존에 저장된 도착 노드까지의 최단 거리(distance[next.vertex])를 비교하여 더 짧은 경로가 있는지 확인합니다.
->나는 Integer.MAX_VALUE 으로 골랐다. 다익스트라의 시작점은 자기 자신까지의 거리가 0이므로, pq에 new Node(K, 0)을 넣는 게 맞다.
