반응형
📖 문제
https://www.acmicpc.net/problem/5972
💡 풀이 방식
• 다익스트라
전형적인 다익스트라 문제다,,
- 최소 여물 비용 배열을 모두 5만*1000 + 1 이상의 큰 값으로 채운다.
- 그래프 정보를 양방향으로 입력받는다.
- 시작점 1부터 목적지 N까지 최소 비용으로 이동하도록 다익스트라를 진행한다.
🔺 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
|
import java.util.*;
import java.io.*;
public class Main {
static int N,M;
static List<Node>[] graph; // 인접 리스트
static int[] dist; // 최소 여물 배열
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(), " ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
// 초기화 - 인접 리스트, 최소 여물 배열, 방문 표시 배열
graph = new ArrayList[N+1];
for(int i = 1 ; i <= N ; i++) graph[i] = new ArrayList<>();
dist = new int[N+1];
Arrays.fill(dist, Integer.MAX_VALUE); // 5만 * 1000 +1
visited = new boolean[N+1];
while(M --> 0) {
st = new StringTokenizer(br.readLine(), " ");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
// 양방향
graph[a].add(new Node(b,c));
graph[b].add(new Node(a,c));
}
System.out.println(dijkstra());
}
private static int dijkstra() {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(1, 0));
dist[1] = 0; // 시작 노드
while(!pq.isEmpty()) {
Node now = pq.poll();
if(visited[now.e]) continue;
visited[now.e] = true;
for(Node next : graph[now.e]) {
if(dist[next.e] > dist[now.e] + next.v) { // 최소 여물 갱신
dist[next.e] = dist[now.e] + next.v;
pq.add(new Node(next.e, dist[next.e]));
}
}
}
return dist[N];
}
}
class Node implements Comparable<Node> {
int e, v;
public Node(int e, int v) {
this.e = e;
this.v = v;
}
// 여물 비용 기준 오름차순 정렬
@Override
public int compareTo(Node n) {
return this.v - n.v;
}
}
|
cs |
➕ 다른 풀이 방식
우선순위 큐를 여물 비용 기준 오름차순 정렬할 때 이렇게 해도 된다.
PriorityQueue<Node> queue = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
V |
반응형
'코테 > 백준' 카테고리의 다른 글
[백준/JAVA] 16943번: 숫자 재배치 (0) | 2024.05.24 |
---|---|
[백준/JAVA] 14620번: 꽃길 (0) | 2024.05.20 |
[백준/JAVA] 17396번: 백도어 (0) | 2024.05.17 |
[백준/JAVA] 15723번: n단 논법 (0) | 2024.05.16 |
[백준/JAVA] 1504번: 특정한 최단 경로 (0) | 2024.05.15 |