반응형
https://www.acmicpc.net/problem/1238
✅ 골드 Ⅲ
🔶 풀이
각 각의 마을에서 파티가 열린 마을 X를 방문했다가 다시 돌아왔을 때 가장 많이 시간을 소비한 학생을 구하라.
모든 가중치가 양수이고, 한 정점에서 다른 모든 정점까지의 최단 거리를 구해야하므로 다익스트라.
다익스트라를 두 번 나누어서 해결했다.
1. X에서 각 마을까지의 최단 거리
2. 각 마을에서 X까지의 최단 거리 (역방향)
위 두가지를 구한 후에 더한 값 중 최대값이 정답이 된다.
1번 방법은 X를 출발점으로 두고 다익스트라 알고리즘을 진행해주면 된다.
문제는 2번 방법이다.
각 마을마다 다익스트라 알고리즘을 진행하면 효율성이 너무 떨어진다.
때문에 기존 입력값에서 출발 마을과 도착 마을을 반대로 입력해서 한 번의 다익스트라 알고리즘으로 해결할 수 있다.
출발 마을과 도착 마을을 반대로 입력함으로써 1번 방법과 동일하게 마을 X를 출발지로 둘 수 있음으로 한 번의 다익스트라 알고리즘으로 최단 거리를 구할 수 있다.
<최종코드>
import java.io.*;
import java.util.*;
public class Main {
static int N, X;
static int INF = 987654321;
public static class Node implements Comparable<Node> {
int end, sec;
public Node(int end, int sec) {
this.end = end;
this.sec = sec;
}
public int compareTo(Node o) {
return this.sec - o.sec;
}
}
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()); // 마을 개수
int M = Integer.parseInt(st.nextToken()); // 도로 개수
X = Integer.parseInt(st.nextToken()); // 파티가 열리는 마을 번호
ArrayList<Node>[] arrList = new ArrayList[M+1]; // X에서 각 마을로
ArrayList<Node>[] revList = new ArrayList[M+1]; // 각 마을에서 X로
for (int i=1; i<=M; i++) {
arrList[i] = new ArrayList<>();
revList[i] = new ArrayList<>();
}
for (int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
arrList[s].add(new Node(e, v));
revList[e].add(new Node(s, v));
}
for (int i=1; i<=M; i++) {
Collections.sort(arrList[i]);
Collections.sort(revList[i]);
}
int[] A = dijkstra(arrList);
int[] B = dijkstra(revList);
int ans = 0;
for (int i=1; i<=N; i++) {
ans = Math.max(ans, A[i] + B[i]);
}
System.out.println(ans);
}
public static int[] dijkstra(ArrayList<Node>[] List) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(X, 0));
boolean[] visited = new boolean[N+1];
int[] dp = new int[N+1];
Arrays.fill(dp, INF);
dp[X] = 0;
while (!pq.isEmpty()) {
Node cur = pq.poll();
for (Node next : List[cur.end]) {
if (!visited[next.end] && dp[next.end] > dp[cur.end] + next.sec) {
dp[next.end] = dp[cur.end] + next.sec;
pq.add(new Node(next.end, dp[next.end]));
}
}
}
return dp;
}
}
반응형
'알고리즘 > 최소신장트리(MST) & 다익스트라' 카테고리의 다른 글
[백준]JAVA - 4485번: 녹색 옷 입은 애가 젤다지? (0) | 2023.04.26 |
---|---|
[백준]JAVA - 1976번: 여행 가자 (0) | 2023.04.20 |
[백준]JAVA - 20926번: 얼음 미로 (0) | 2023.03.07 |
[백준]JAVA - 1504번: 특정한 최단 경로 (0) | 2022.12.08 |
[백준]JAVA - 1197번: 최소 스패닝 트리 (0) | 2022.11.07 |