728x90
https://www.acmicpc.net/problem/1238
🤔 문제 접근
처음 떠올린 풀이 방법은 N개의 마을에서 파티가 열리는 X번 마을까지의 최소 거리를 구하고
X번 마을에서 각각의 N개의 마을까지의 최소 거리를 구해 더한 뒤, 최소 값들 중 최대 값을 구하는 것이었다.
A 마을에서 B마을까지의 최소 거리를 구하기 위해 최단 경로 탐색 알고리즘인 다익스트라 알고리즘을 사용했다.
하지만 위 풀이 방식으로 문제를 풀 경우 우선순위 큐를 사용한 다익스트라 알고리즘을 이용하더라도
N * (N+M)logN의 시간 복잡도를 갖게되어 최대 데이터 값으로 생각했을 때 1억을 초과하므로
시간 초과가 우려되었다.
따라서 각각의 마을에서 X번째 마을까지의 거리 정보를 반대로 저장하여
1. 역으로 X번째 마을에서 각 마을까지의 최소 거리를 구하고
2. 원래 구하려고했었던 X번째 마을에서 각 마을까지의 최소 거리를 구해
1번과정에서 구한 각각의 최소 거리값들과 2번과정에서 구한 최소 거리값들을 더해
최대 값을 구하고자 했다.
이 방법을 사용할 경우 1번과정에서 마을 수 만큼 반복하여 다익스트라 알고리즘을 수행하지 않아도 되어
실행 시간을 대폭 줄일 수 있었다.
=> (1번과정) + (2번과정) = 1 * (N + M)log N + 1* (N+M) log N = 2 * (N+M) logN
1번과정과 2번과정을 수행하는 코드가 중복된 내용이 많아서
flag 변수를 이용했다.
🚨CODE
import java.io.*;
import java.util.*;
public class Main {
static ArrayList<Node>[] road;
static ArrayList<Node>[] reverse;
static int[] dist;
static int flag = 0;
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()); // 학생수
int m = Integer.parseInt(st.nextToken()); // 단방향 도로 수
int x = Integer.parseInt(st.nextToken()); // 파티하는 마을
road = new ArrayList[n+1];
reverse = new ArrayList[n+1];
int[] result = new int[n+1];
for(int i = 1; i<=n; i++) {
road[i] = new ArrayList<>();
reverse[i] = new ArrayList<>();
}
for(int i = 0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
road[a].add(new Node(b,v));
reverse[b].add(new Node(a,v));
}
boolean[] visit = new boolean[n+1];
dist = new int[n+1];
for(int i = 1; i<=n; i++) {
dist[i] = Integer.MAX_VALUE;
}
dist[x] = 0;
check(x, visit);
flag += 1;
for(int i = 1; i<=n; i++) {
result[i] = dist[i];
}
for(int i = 1; i<=n; i++) {
dist[i] = Integer.MAX_VALUE;
}
dist[x] = 0;
Arrays.fill(visit, false);
check(x, visit);
for(int i = 1; i<=n; i++) {
result[i] += dist[i];
}
int answer = 0;
for(int i = 1; i<=n; i++) {
answer = Math.max(result[i], answer);
}
System.out.println(answer);
}
public static void check(int start, boolean[] visit) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.add(new Node(start, 0));
if(flag == 0) {
while(!pq.isEmpty()) {
Node curNode = pq.poll();
if(visit[curNode.end])
continue;
visit[curNode.end] = true;
for(Node node : reverse[curNode.end]) {
if(dist[node.end] > dist[curNode.end] + node.value) {
dist[node.end] = dist[curNode.end] + node.value;
pq.add(new Node(node.end, dist[node.end]));
}
}
}
}
else {
while(!pq.isEmpty()) {
Node curNode = pq.poll();
if(visit[curNode.end])
continue;
visit[curNode.end] = true;
for(Node node : road[curNode.end]) {
if(dist[node.end] > dist[curNode.end] + node.value) {
dist[node.end] = dist[curNode.end] + node.value;
pq.add(new Node(node.end, dist[node.end]));
}
}
}
}
}
}
class Node implements Comparable<Node>{
int end;
int value;
Node(int end, int value) {
this.end = end;
this.value = value;
}
public int compareTo(Node n) {
return value - n.value;
}
}
728x90
반응형
'코딩테스트' 카테고리의 다른 글
[Gold4-JAVA] 백준 1967 - 트리의 지름 (1) | 2024.03.22 |
---|---|
[JAVA] 백준 11048 - 이동하기 (0) | 2024.03.19 |
[JAVA] 백준 9465 - 스티커 (0) | 2024.03.11 |
[JAVA] 백준 1932 - 정수 삼각형 (0) | 2024.03.10 |
[JAVA] 백준 2156 - 포도주 시식 (0) | 2024.03.06 |