링크
https://www.acmicpc.net/problem/1753
문제 설명
정답률 25.588%
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.
입력 예제
- 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000)
- 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다.
- 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다.
- 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다.
- 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다.
- u와 v는 서로 다르며 w는 10 이하의 자연수이다.
- 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6
출력 예제
- 첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다.
- 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.
0
2
3
7
INF
풀이
시작점과 다른 노드와의 최단 거리를 구하는 문제로, 다익스트라 알고리즘으로 해결할 수 있다. 간선에 관한 데이터가 입력값으로 주어지므로 목적지와 가중치를 담은 Edge 클래스를 생성한다.
static class Edge {
int to;
int weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
public int getWeight() {
return weight;
}
}최단 경로를 저장하기 위한 각 노드의 누적 거리 배열을 생성한다. 최솟값으로 갱신해나가야 하므로 최댓값으로 저장해둔다.
int[] dist = new int[V + 1]; //각 노드까지의의 최단 거리를 저장할 배열
Arrays.fill(dist, Integer.MAX_VALUE);인접 리스트를 구성한 뒤 다익스트라 알고리즘을 수행하는데 예제를 기준으로 생각해보면 그래프는 다음과 같다.
우선 시작 노드 1을 기준으로 거리를 갱신하면 다음과 같다.
- [0, 2, 3, INF, INF] (1번 노드 방문 처리)
그다음 방문하지 않은 노드 중 최소 거리의 노드는 2번이다. 3번 노드의 경우 기존의 저장된 거리보다 갱신하려는 거리가 더 크므로 (3 < 6) 갱신하지 않고, 4번 노드만 갱신한다.
- [0, 2, 3, 7, INF] (2번 노드 방문 처리)
그다음 방문할 노드는 3번 노드이다. 3번 노드에서 갈 수 있는 노드는 4번 노드 뿐인데 기존 값이 더 작으므로 갱신하지 않는다.
- [0, 2, 3, 7, INF] (3번 노드 방문 처리)
다음 방문할 노드는 4번이지만 방문할 수 없는 노드가 없다.
- [0, 2, 3, 7, INF] (4번 노드 방문 처리)
마지막으로 5번 노드도 시작 노드인 1번에서 방문할 수 없다.
- [0, 2, 3, 7, INF] (5번 노드 방문 처리)
다익스트라는 우선순위 큐를 사용하는데 가중치가 낮은 노드부터 정렬하기 위해 다음과 같이 생성한다.
PriorityQueue<Edge> queue = new PriorityQueue<>(Comparator.comparingInt(Edge::getWeight));코드
import static java.util.Comparator.comparingInt;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
//백준
public class Main {
static List<List<Edge>> adjList = new ArrayList<>();
static boolean[] visited;
static int[] dist;
public static void main(String[] args) throws IOException {
System.setIn(new FileInputStream("src/input.txt"));
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()); //시작 정점
visited = new boolean[V + 1];
dist = new int[V + 1]; //최단 거리를 저장할 배열
//인접 리스트 초기화
for (int i = 0; i <= V; i++) {
adjList.add(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()); //u -> v 가중치
adjList.get(u).add(new Edge(v, w));
}
dijkstra(K);
for (int i = 1; i <= V; i++) {
if (visited[i]) {
System.out.println(dist[i]);
} else {
System.out.println("INF");
}
}
}
static void dijkstra(int node) {
//거리 배열을 최댓값으로 초기화
Arrays.fill(dist, Integer.MAX_VALUE);
//간선의 가중치를 오름차순으로 정렬하는 우선순위 큐 생성
PriorityQueue<Edge> queue = new PriorityQueue<>(comparingInt(Edge::getWeight));
queue.add(new Edge(node, 0));
dist[node] = 0;
while (!queue.isEmpty()) {
Edge cur = queue.poll();
int curNode = cur.to;
//방문하지 않은 노드일 경우
if (!visited[curNode]) {
visited[curNode] = true; //현재 노드 방문 처리
//인접 노드 탐색
for (Edge next : adjList.get(curNode)) {
int nextNode = next.to;
int nextWeight = next.weight;
int newDist = dist[curNode] + nextWeight;
//기존 거리가 현재 거리보다 클 경우 갱신
if (dist[nextNode] > newDist) {
dist[nextNode] = newDist;
//누적 거리를 가중치로 하여 간선 추가
queue.add(new Edge(nextNode, dist[nextNode]));
}
}
}
}
}
static class Edge {
int to;
int weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
public int getWeight() {
return weight;
}
}
}
백엔드