[백준/JAVA] 1916번: 최소비용 구하기
🔺 문제
1916번: 최소비용 구하기
첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그
www.acmicpc.net
🔺 코드
- 코드1)
|
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
79
80
81
82
83
84
85
86
|
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[] D; // 🎈 최단 경로 배열 🎈
static ArrayList<Node>[] A; // 인접 리스트
static boolean[] visited; // 방문 배열
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
visited = new boolean[N+1];
// 최단 경로 배열 초기화
D = new int[N+1];
Arrays.fill(D, Integer.MAX_VALUE);
// 인접 리스트 초기화
A = new ArrayList[N+1];
for(int i = 0 ; i <= N ; i++) {
A[i] = new ArrayList<>();
}
// 그래프 입력 받기
while(M --> 0) {
st = new StringTokenizer(br.readLine()," ");
int S = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
A[S].add(new Node(E, V));
}
// 출발 도시, 도착 도시 입력 받기
st = new StringTokenizer(br.readLine()," ");
int startCity = Integer.parseInt(st.nextToken());
int endCity = Integer.parseInt(st.nextToken());
// 다익스트라 수행
System.out.println(dijkstra(startCity, endCity));
}
// 다익스트라
public static int dijkstra(int start, int end) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start, 0));
D[start] = 0;
while(!pq.isEmpty()) {
Node nowNode = pq.poll();
if(!visited[nowNode.node]) {
visited[nowNode.node] = true;
for(Node next : A[nowNode.node]) {
if(!visited[next.node] && D[next.node] > D[nowNode.node] + next.value) {
D[next.node] = D[nowNode.node] + next.value;
pq.add(new Node(next.node, D[next.node]));
}
}
}
}
return D[end];
}
}
class Node implements Comparable<Node>{
int node, value;
Node(int node, int value) {
this.node = node;
this.value = value;
}
@Override
public int compareTo(Node e) {
return this.value - e.value;
}
}
|
cs |
- 코드2)
|
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
79
80
|
import java.util.*;
import java.io.*;
public class Main {
static int N, M;
static int[] D; // 최단 경로 배열
static ArrayList<Node>[] A; // 인접 리스트
static boolean visited[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
M = Integer.parseInt(br.readLine());
visited = new boolean[N+1];
D = new int[N+1];
Arrays.fill(D, Integer.MAX_VALUE);
A = new ArrayList[N+1];
for(int i = 0 ; i <= N ; i++) {
A[i] = new ArrayList<>();
}
while(M --> 0) {
st = new StringTokenizer(br.readLine()," ");
int S = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
int V = Integer.parseInt(st.nextToken());
A[S].add(new Node(E, V));
}
st = new StringTokenizer(br.readLine()," ");
int startCity = Integer.parseInt(st.nextToken());
int endCity = Integer.parseInt(st.nextToken());
System.out.println(dijkstra(startCity, endCity));
}
public static int dijkstra(int start, int end) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start, 0));
D[start] = 0;
//visited[start] = true;
while(!pq.isEmpty()) {
Node nowNode = pq.poll();
// ** 변경된 부분 **
if(visited[nowNode.node]) continue; // 중복 방지
visited[nowNode.node] = true;
for(Node next : A[nowNode.node]) {
if(D[next.node] > D[nowNode.node] + next.value) {
D[next.node] = D[nowNode.node] + next.value;
pq.offer(new Node(next.node, D[next.node]));
}
}
}
return D[end];
}
}
class Node implements Comparable<Node>{
int node, value;
Node(int node, int value) {
this.node = node;
this.value = value;
}
@Override
public int compareTo(Node e) {
return value - e.value;
}
}
|
cs |
처음에 여기서 다익스트라 실행할 때,
우선순위 큐에 넣고 해당 인덱스를 48번째 줄처럼 바로 방문 표시했었는데 (visited[start] = true;)
이상한 답이 나왔었다...
그래서 저거 지워봤더니 결과값 잘 나옴💦💦
✅ 해결 아이디어
✔ 다익스트라 - BFS랑 유사. 우선순위 큐 사용
최단 경로 배열은 이렇게 나온다.
🔺 다른 풀이들
- 보니까 다익스트라 메소드 안에서 방문 배열 선언하고 초기화 해줘도 됨.
[BOJ] 백준 1916번 : 최소비용 구하기 (JAVA)
문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 M개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고 한다. A번째
steady-coding.tistory.com
- 인접 행렬 사용하심 & 그래프에서 연결된 다음 정점들 방문할 때, Iterator 사용하심
[백준 1916번 최소비용 구하기] JAVA 풀이 (다익스트라)
문제링크 이 문제에서는 N개의 정점과 M개의 음이아닌 가중치를 가지는 간선을 준다. 이때 특정 정점사이로 이동하는 최소 가중치의 합을 구해야한다. 소스코드 ```java import java.io.; import java.util.;
rst0070.github.io
- 과정 설명 굿 (복습용)
백준 1916번 : 최소비용 구하기 java
이 문제는 다익스트라 알고리즘을 이용하는 문제입니다. 다익스트라 알고리즘에 대하여 설명드리겠습니다. 예제 1번을 예시로 다익스트라 알고리즘을 설명드리겠습니다. 예제 1번에서는 왼쪽
dy-coding.tistory.com
- Node 생성하지 않고, int[] 배열 만들어 푸심 & 우선순위 큐 오름차순 정렬도 람다식 사용
로그인
www.acmicpc.net
💬 느낀 점
이제 가중치 갖는 인접 리스트를 어찌저찌 혼자 작성할 줄 알게 되었다!
| 1회독 | 2회독 | 3회독 | 4회독 | 5회독 |
| V | 230522 | 230626 | 240518 |
(참고)
✔ 1753번: 최단 경로
[백준/JAVA] 1753번: 최단경로
🔺 문제 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정
bono039.tistory.com