알고리즘/백준
[백준] 1753. 최단경로 (자바 JAVA)
spacelife
2025. 4. 9. 12:17
728x90
반응형
문제
방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.
출력
첫째 줄부터 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
접근 방법 🧐
가중치가 존재하는 그래프이고 출발점이 하나로 고정되어서 최단 거리를 구하는 문제이므로 다익스트라로 풀어야겠다고 생각했다.
1. 인접 리스트로 각 노드별로 이동 가능한 노드들을 저장한다.
2. 각 노드별 최단 거리를 저장하는 distances 배열을 만들고 시작점 K를 제외하고 모두 Integer.MAX_VALUE로 초기화한다.
3. 다익스트라 알고리즘을 수행하는 dijkstra(K)를 호출한다.
4. dijkstra 메서드에서는 다음과 같이 수행한다.
(1) 우선순위 큐(PriorityQueue) 를 사용하여 가장 최단 거리가 짧은 정점부터 탐색한다.
(2) poll()을 통해 최단 거리 정점을 가져온다.
(3) 현재 정점과 연결된 모든 정점(next)을 탐색하는데, 현재 정점을 거쳐 가는 것이 더 짧은 경로라면 distances[next.number]를 갱신한다.
(4) 갱신된 정점은 우선순위 큐에 삽입하고 최단 거리 기준으로 탐색을 계속 진행한다.
내가 쓴 코드 ✍️
첫번째 시도
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static class Node implements Comparable<Node> {
int number;
int cost;
public Node(int number, int cost) {
this.number = number;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return this.cost - o.cost;
}
}
private static int V, E;
private static List<List<Node>> graph;
private static int[] distances;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(br.readLine());
graph = new ArrayList<>();
distances = new int[V + 1];
for (int i = 0; i <= V; i++) {
graph.add(new ArrayList<>());
if (i == K) distances[i] = 0;
else distances[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph.get(from).add(new Node(to, cost));
}
dijkstra(K);
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= V; i++) {
if (distances[i] == Integer.MAX_VALUE) {
sb.append("INF").append("\n");
} else {
sb.append(distances[i]).append("\n");
}
}
System.out.println(sb);
}
private static void dijkstra(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0));
distances[start] = 0;
while (!pq.isEmpty()) {
Node now = pq.poll();
for (Node next: graph.get(now.number)) {
if (distances[now.number] + next.cost < distances[next.number]) {
distances[next.number] = distances[now.number] + next.cost;
pq.offer(new Node(next.number, next.cost));
}
}
}
}
}
위에 작성한 코드를 작성하면 다음과 같이 시간 초과가 발생했는데,
문제가 뭐였니 해서 디버깅해보니 노드 방문 여부 체크를 안해서 pq에 너무 많은 노드가 들어가서 불필요한 탐색이 이루어지고 효율성이 떨어진 것이었다...
두번째 시도
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
private static class Node implements Comparable<Node> {
int number;
int cost;
public Node(int number, int cost) {
this.number = number;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return this.cost - o.cost;
}
}
private static int V, E;
private static List<List<Node>> graph;
private static int[] distances;
private static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(br.readLine());
graph = new ArrayList<>();
distances = new int[V + 1];
for (int i = 0; i <= V; i++) {
graph.add(new ArrayList<>());
if (i == K) distances[i] = 0;
else distances[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph.get(from).add(new Node(to, cost));
}
visited = new boolean[V + 1];
dijkstra(K);
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= V; i++) {
if (distances[i] == Integer.MAX_VALUE) {
sb.append("INF").append("\n");
} else {
sb.append(distances[i]).append("\n");
}
}
System.out.println(sb);
}
private static void dijkstra(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0));
distances[start] = 0;
visited[start] = true;
while (!pq.isEmpty()) {
Node now = pq.poll();
int nowNodeNumber = now.number;
int nowCost = now.cost;
visited[nowNodeNumber] = true;
for (Node next: graph.get(nowNodeNumber)) {
if (!visited[next.number]) {
if (distances[nowNodeNumber] + next.cost < distances[next.number]) {
distances[next.number] = distances[nowNodeNumber] + next.cost;
pq.offer(new Node(next.number, distances[nowNodeNumber] + next.cost));
}
}
}
}
}
}
2번째 시도로 visited 배열을 만들고 다음으로 이동할 수 있는 노드를 방문했는지의 여부를 체크해서 pq에 노드를 넣어줬더니
정답이 되었다아아!!!
좀 더 간결한 코드
굳이 visited 배열을 만들지 않고 distances 배열을 활용하여 현재 꺼낸 노드가 기존 저장된 최단 거리를 비교해서 현재 꺼낸 노드가 기존 저장된 최단 거리보다 크면 continue해서 중복 탐색을 방지하고 효율성을 올릴 수 있다. 이렇게 풀어도 정답 처리된다.
import java.io.*;
import java.util.*;
public class Main {
private static class Node implements Comparable<Node> {
int number;
int cost;
public Node(int number, int cost) {
this.number = number;
this.cost = cost;
}
@Override
public int compareTo(Node o) {
return Integer.compare(this.cost, o.cost);
}
}
private static int V, E;
private static List<List<Node>> graph;
private static int[] distances;
private static final int INF = Integer.MAX_VALUE;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
V = Integer.parseInt(st.nextToken());
E = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(br.readLine());
graph = new ArrayList<>();
distances = new int[V + 1];
for (int i = 0; i <= V; i++) {
graph.add(new ArrayList<>());
distances[i] = INF; // 모든 노드를 무한대로 초기화
}
distances[K] = 0; // 시작 노드는 0으로 설정
for (int i = 0; i < E; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
graph.get(from).add(new Node(to, cost));
}
dijkstra(K);
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= V; i++) {
sb.append(distances[i] == INF ? "INF" : distances[i]).append("\n");
}
System.out.print(sb);
}
private static void dijkstra(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0));
while (!pq.isEmpty()) {
Node now = pq.poll();
int nowNode = now.number;
int nowCost = now.cost;
// 현재 꺼낸 노드가 기존 저장된 최단 거리보다 크면 무시 (중복 탐색 방지)
if (nowCost > distances[nowNode]) continue;
for (Node next : graph.get(nowNode)) {
int newDist = distances[nowNode] + next.cost;
if (newDist < distances[next.number]) {
distances[next.number] = newDist;
pq.offer(new Node(next.number, newDist)); // 갱신된 거리로 삽입
}
}
}
}
}
구독과 공감♡♡은 블로그 운영에 큰 힘이 됩니다!
긍정적인 댓글 남겨주시면 감사드리며,
보완해야 할 점이 있으면 댓글로 남겨주셔도 좋습니다!
728x90
반응형