[백준]1238번 파티
N개의 마을이 존재
- 각 마을에 한 명의 학생이 살고 있다.
- 단방향 도로
- 도로의 가중치 : Ti
- 어떤 마을에서 출발한 학생은 다시 자신의 마을로 돌아와야 함
- 파티가 열리는 마을 → X번 마을
N명의 학생들 중 , 오고 가는데 가장 많은 시간을 소비하는 학생은 누구인가?
풀이 생각
- N은 1000 이하, M은 10000이하
- A → B 로 가는 도로의 개수는 최대 1개 이다.
- 모든 학생들에 대해 생각 해 보아야 할까?
-
모든학생에 대해, 디익스트라를 두 번씩 수행해야 한다.
-
A → X 까지 가는 데 최단 거리 구하는 알고리즘
다익스트라
—> O(V^2logE) 의 시간복잡도
- Priority Queue에 대한 operation들은 O(nlogn) 의 complexity를 갖는다.
- 현재 가장 적은 cost를 가진 노드를 선택 : Priority Queue로부터 pop
- 해당 노드가 갖고 있는 cost 값이, 현재 table상에 cost값보다 큰지 확인 → 크다면 pass한다.
- 해당 노드의 인접노드들까지의 cost들을 계산
- IF, 더 적은 cost를 갖게 되는 인접 노드가 존재한다면 → insert into Priority Queue
- 즉, PQ에는 노드의 개수 V만큼 들어가게 될 것.
-
N명의 학생들에 대해, 각 학생이
- 학생 → X
- X → 학생
-
2 x V^2logN → 이기 때문에 2 x 1000000 x 4 → 가능하다.
-
첫번째
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class Main{
// 마을의 수 == 학생의 수
public static int n;
// 파티가 열리는 마을 x
public static int x;
// 최단 거리 테이블
public static int[] dist = new int[1000];
// 그래프
public static List<int[]>[] graph = new ArrayList[1000];
// 가장 오래 걸리는 학생의 소요시간
public static int max = 0;
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static StringTokenizer st;
public static void setting() throws IOException{
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
x = Integer.parseInt(st.nextToken())-1;
// graph init
for(int i=0;i<n;i++)
graph[i] = new ArrayList<>();
int v1=0,v2=0,w=0;
for(int i=0;i<m;i++){
st = new StringTokenizer(br.readLine());
v1 = Integer.parseInt(st.nextToken())-1;
v2 = Integer.parseInt(st.nextToken())-1;
w = Integer.parseInt(st.nextToken());
graph[v1].add(new int[]{v2,w});
}
}
public static void initTable(int src){
Arrays.fill(dist,Integer.MAX_VALUE);
dist[src] = 0;
}
public static void solve(){
// 각 학생에 대해 , 학생 -> X, X-> 학생 모두를 구해야함
int c1 =0,c2=0;
for(int i =0;i<n;i++){
// i -> x
initTable(i);
c1 = findCost(i,x);
// System.out.println((i+1)+"->"+(x+1)+" : "+c1);
// x -> i
initTable(x);
c2 = findCost(x,i);
// System.out.println((x+1)+"->"+(i+1)+" : "+c2);
max = Math.max(c1+c2,max);
}
}
// src ->dest 까지 가는데 걸리는 최단 거리
public static int findCost(int src, int dest){
PriorityQueue<int[]> q = new PriorityQueue<int[]>((int[] o1, int[] o2)->{return o1[1]-o2[1];});
q.add(new int[]{src,0});
int[] cur = null, adj = null;
int len = 0, temp =0;
while(q.isEmpty()==false){
cur = q.poll();
if(cur[1] > dist[cur[0]]) continue;
if(cur[0] == dest) break;
// 인접 노드들 확인
len = graph[cur[0]].size();
for(int i=0;i<len;i++){
adj = graph[cur[0]].get(i);
if((temp = adj[1] + cur[1]) < dist[adj[0]] ){
q.add(new int[]{adj[0],temp});
dist[adj[0]] = temp;
}
}
}
// 가장 최소 거리 확인
return dist[dest];
}
public static void print(){
Arrays.stream(dist).filter(i -> i!=Integer.MAX_VALUE).toArray();
}
public static void main(String[] args) throws IOException{
setting();
solve();
System.out.println(max);
}
}두 번째
- 현재는 모든 start에 대해 디익스트라 메소드를 실행시키는 방법을 사용하고 있음.
- a→x
- x→a
- 즉 각 노드에 대해 두 번의 디익스트라를 하고 있다.
그런데!! 생각해 보면
- x를 시작점으로 한 디익스트라를 한 번만 해도
- x 부터 모든 지점까지의 최소 거리를 구하는 것이 가능하다.
- 그런데 현재 그래프로는 결국
- 모든 노드에 대해 a→x는 수행해야 한다.
여기서 더 나아간 생각을 할 수 있다.
- x를 시작점으로 한 디익스트라를 한 번만 해도
- x로부터 모든 지점까지의 최소거리를 구할 수 있다
라고 했다.
- 이는 x→a 까지의 최소 거리를 구하는 것이다.
그렇다면 a → x 도 “x하나만을 중심으로 할 수 있는 방법 없나???”
문제에서 주어진 것은 단방향 그래프
- 문제에서 주어진 것을 그대로로한 그래프를 사용한다면
- x→a 로의 디익스트라를 할 수 있고, 이를 통해, x로부터 각 노드까지의 최소 거리를 구할 수가 있다.
- 문제에서 주어진 방향을 반대로한 그래프를 사용한다면
- 이 그래프에서의 x→a는 , 결국 원래 그래프에서 원하던 a→x가 되는 것이다.
- 그런데, 이 그래프에서는 x → a로의 디익스트라 한 번에, 모든 노드로부터 x까지의 최소 거리를 구할 수 있게 되는 것이다.
따라서
- 두 종류의 그래프를 사용하여 각각에서, x를 시작점으로 하는 디익스트라를 수행한다. 즉, 단 두번만 디익스트라 함수를 호출 해 주면 된다.
- 이 디익스트라는, PriorityQueue가 empty 할 때 까지 모두 수행하여도 된다.
- 이 결과, x부터 각 노드까지의 최소거리를 구할 수 있다.
package coding;
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class Main{
// 마을의 수 == 학생의 수
public static int n;
// 파티가 열리는 마을 x
public static int x;
// 최단 거리 테이블
public static int[] dist = new int[1000];
public static int[] rdist = new int[1000];
// 그래프
public static List<int[]>[] graph = new ArrayList[1000];
public static List<int[]>[] rgraph = new ArrayList[1000];
// 가장 오래 걸리는 학생의 소요시간
public static int max = 0;
public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
public static StringTokenizer st;
public static void setting() throws IOException{
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
x = Integer.parseInt(st.nextToken())-1;
// graph init
for(int i=0;i<n;i++) {
graph[i] = new ArrayList<>();
rgraph[i] = new ArrayList<>();
}
int v1=0,v2=0,w=0;
for(int i=0;i<m;i++){
st = new StringTokenizer(br.readLine());
v1 = Integer.parseInt(st.nextToken())-1;
v2 = Integer.parseInt(st.nextToken())-1;
w = Integer.parseInt(st.nextToken());
graph[v1].add(new int[]{v2,w});
rgraph[v2].add(new int[]{v1,w});
}
}
public static void initTable(int src,int[] t){
Arrays.fill(t,Integer.MAX_VALUE);
t[src] = 0;
}
public static void solve(){
// 각 학생에 대해 , 학생 -> X, X-> 학생 모두를 구해야함
int c1 =0,c2=0;
initTable(x,dist);
initTable(x,rdist);
findCost(x,graph,dist);
findCost(x,rgraph,rdist);
for(int i =0;i<n;i++){
max = Math.max(dist[i]+ rdist[i],max);
}
}
// src 로부터 모든 노드까지의 최단거리
public static void findCost(int src,List<int[]>[] g, int[] t){
PriorityQueue<int[]> q = new PriorityQueue<int[]>((int[] o1, int[] o2)->{return o1[1]-o2[1];});
q.add(new int[]{src,0});
int[] cur = null, adj = null;
int len = 0, temp =0;
while(q.isEmpty()==false){
cur = q.poll();
if(cur[1] > t[cur[0]]) continue;
// 인접 노드들 확인
len = g[cur[0]].size();
for(int i=0;i<len;i++){
adj = g[cur[0]].get(i);
if((temp = adj[1] + cur[1]) < t[adj[0]] ){
q.add(new int[]{adj[0],temp});
t[adj[0]] = temp;
}
}
}
}
public static void main(String[] args) throws IOException{
setting();
solve();
System.out.println(max);
}
}