IT/알고리즘
백준 1238 파티
어센트
2020. 4. 7. 21:02
https://www.acmicpc.net/problem/1238
1238번: 파티
문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다. 이 도로들은 단방향이기 때
www.acmicpc.net
배운점
단방향 그래프에서 다익스트라 알고리즘을 활용하여 문제를 해결하는 문제였다.
다익스트라 알고리즘이 어떤 방식으로 구현되는지에 대해 알고 실제로 코드를 작성하여 문제를 풀어본 건 3학년 1학기 알고리즘 시간이었으니... 거의 1년이 다되가는 것 같다.
덕분에 다익스트라를 구현하는데 많은 시간이 걸렸다.
- 방문했는 지를 확인하는 배열vis 과 시작노드(start)부터 그 노드까지의 거리를 저장할 배열 dArr을 만들었다.
- dArr을 최대로 초기화 vis를 false로 전부초기화
- 시작노드와 인접한 노드 거리 계산 dArr 수정
- 방문하지 않고 인접한 노드를 찾으며 dArr의 값이 가장 적은 노드(index)로 방문
- 이 가장 적은 노드(index)와 인접하고 방문하지않은 노드를 찾고 현재까지 dArr[j]와 이 index를 거쳤을 경우(Arr[index][j]+dArr[index])를 비교하여 더 짧은 값으로 수정
- 모든 노드를 확인하기위해 위 모든 과정 n-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
|
package 번호별;
import java.io.*;
import java.util.*;
public class Pro1238 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), x = Integer.parseInt(st.nextToken());
int[][] Arr = new int[n + 1][n + 1];
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int dis = Integer.parseInt(st.nextToken());
Arr[start][end] = dis;
}
int ans = -1;
for (int i = 1; i < n + 1; i++) {
boolean[] vis = new boolean[n + 1];
int[] dArr = new int[n + 1];
ans = Math.max(ans,fun(Arr, dArr, vis, i, x) + fun(Arr,dArr,vis,x,i));
}
System.out.println(ans);
}
static int fun(int[][] Arr, int[] dArr, boolean[] vis, int start, int endIndex) {
for (int i = 1; i < dArr.length; i++) {
dArr[i] = Integer.MAX_VALUE;
vis[i] = false;
}
dArr[start] = 0;
vis[start] = true;
for (int i = 1; i < Arr.length; i++) {
if (!vis[i] && Arr[start][i] > 0) { //start노드와 인접한 노드거리 설정
dArr[i] = Arr[start][i];
}
}
for (int i = 1; i < Arr.length - 1; i++) { //모든 노드 돌아보기
int min = Integer.MAX_VALUE;
int index = -1;
for (int j = 1; j < Arr.length; j++) {
if (!vis[j] && dArr[j] != Integer.MAX_VALUE) { //한번도 방문한적없고 인접한경우 즉 인접노드
if (dArr[j] < min) { //가장짧은거리노드를 찾음
min = dArr[j];
index = j;
}
}
}
vis[index] = true; //가장 짧은 노드 방문
for (int j = 1; j < Arr.length; j++) {
if (!vis[j] && Arr[index][j] > 0) { //인접하고 방문한적없는 노드이고
if (dArr[j] > dArr[index] + Arr[index][j]) { // 이노드j를 거칠 경우 더 짧다면?
dArr[j] = dArr[index] + Arr[index][j]; // 거리 수정
}
}
}
}
return dArr[endIndex];
}
}
|
cs |