#1238 파티
난이도 : 골드 3
유형 : 그래프 이론/ 다익스트라(권장) || 플로이드 와샬
1238번: 파티
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어
www.acmicpc.net
▸ 문제
N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.
▸ 입력
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.
모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.
▸ 출력
첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.
문제 풀이
N명의 학생이 X번 마을을 각자 최단 시간으로 오고가는데 가장 오래걸리는 사람을 구하는 문제이다. 이 부분을 읽고 바로 들어야하는 생각은 최단경로 알고리즘인 다익스트라 알고리즘과 플로이드 와샬 알고리즘이다.
🧑🏫 참고 (링크)
- 다익스트라는 한 정점에서 다른 모든 정점의 최단 거리를 구하는 알고리즘
- 플로이드 와샬은 모든 정점에서 다른 모든 정점의 최단 거리를 구하는 알고리즘
조건
- N명 학생 : 1<= N <=1,000
- M개 도로 : 1<= M <=10,000
- T 시간 : 1<= T <=100
해당 문제에서는 한 정점(X번 마을)이 주어졌고 왕복이니 구해야 할 경로는 두 가지이다.
1) 다른 모든 마을 -> X번 마을의 최단 거리,
2) X번 마을 -> 다른 모든 마을의 최단거리
간선은 단방향이므로 다익스트라로 구하면 한 정점 -> 모든 정점이기 때문에 1), 2)를 각각 따로 계산해야 한다.
1)는 그대로 X번 마을로의 최단거리를 계산하고,
2)는 간선의 방향을 바꿔서 최단 거리를 구해야 한다.
☛ 왜냐하면 X번 마을에서 다른 모든 마을의 최단 거리를 그대로 구하면 N-1번의 연산을 돌려야하는데 바꿔서 생각하면 방향만 바꾸면 1)의 방식과 똑같이 X번 마을에서 다른 모든 마을의 최단거리를 한 번의 연산에 구할 수 있다.
그냥 플로이드 와샬 알고리즘을 사용하면 안되나? 지양해야한다. 플로이드 와샬은 모든 정점에서 다른 모든 정점의 최단거리를 한 번에 구해주는 알고리즘이기 때문이다. 단점이있다면 시간이 오래걸리는 것이다. O(n^3)이라서 그래프의 크기가 크면 시간초과가 발생할 것이다.
조건을 보고 최악의 경우 시간이 1,000^3 = 10억... O(n^3)은 n값이 최대 500정도까지가 안전하다고 하다. 코테나 효율성을 따져야하는 과정에서는 정점의 크기가 너무 큰 경우 플로이드 와샬 알고리즘은 사용하지 않는 것이 낫다.
> 물론 무조건적인 것은 없다. 정점의 크기가 적당하고 모든 정점 최단 경로를 구하는 문제면 플로이드 와샬이 더 어울리는 경우도 있다.
그래서 해당 문제는 다익스트라 알고리즘을 사용을 권장한다. 직접 플로이드 와샬과 다익스트라 알고리즘을 둘 다 사용하여 효율성을 비교해보았다.
플로이드 와샬 풀이
i : 시작 정점, j : 도착 정점, k : 중간 정점
for(int k=1; k<n+1; k++) {
for(int i=1; i<n+1; i++) {
for(int j=1; j<n+1; j++) {
if(memo[i][k] + memo[k][j] < memo[i][j]) {
memo[i][j] = memo[i][k] + memo[k][j];
}
}
}
}
플로이드 와샬은 3중 반복문으로 i -> k -> j의 경로를 모두 조회하여 최단 거리를 갱신해서 저장해준다. 시간복잡도는 O(n^3)을 가진다.
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int INF = 1_000_000_000;
public static void main(String[] args) throws IOException{
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());
int[][] memo = new int[n+1][n+1];
for(int i=1; i<n+1; i++) {
for(int j=1; j<n+1; j++) {
if(i==j) {
memo[i][j] =0;
}else {
memo[i][j] = INF;
}
}
}
for(int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
memo[from][to] = cost;
}
for(int k=1; k<n+1; k++) {
for(int i=1; i<n+1; i++) {
for(int j=1; j<n+1; j++) {
if(memo[i][k] + memo[k][j] < memo[i][j]) {
memo[i][j] = memo[i][k] + memo[k][j];
}
}
}
}
int res = Integer.MIN_VALUE;
for(int i=1; i<n+1; i++) {
int dis = memo[i][x] + memo[x][i];
if(dis >res ) {
res = dis;
}
}
System.out.println(res);
}
}
다익스트라 풀이 (권장)
한 정점을 시작으로 그에 대한 다른 모든 정점의 최단 거리를 구한다. 우선순위 큐를 사용하여 거리가 짧은 정점부터 조회하여 최단 거리를 찾는다.
static int[] dijkstra(List<Town>[] list, int start) {
Queue<Town> q = new PriorityQueue<>();
boolean[] check = new boolean[n+1];
int[] dp = new int[n+1];
Arrays.fill(dp, INF);
q.add(new Town(start, 0));
dp[start]=0;
while(!q.isEmpty()) {
Town pos = q.poll();
int to = pos.to;
if(check[to]) continue;
check[to] = true;
for(Town next : list[to]) {
if(dp[to] + next.cost < dp[next.to]) {
dp[next.to] = dp[to] + next.cost;
q.add(new Town(next.to, dp[next.to]));
}
}
}
return dp;
}
미방문 노드 중 출발점으로부터 현재까지 계산된 최단 거리를 가지는 노드를 찾는데 O(VlogV)의 시간이 필요하고 각 노드마다 이웃한 노드의 최단 거리를 갱신할 때 O(ElogV)의 시간이 필요하여 총 시간 복잡도 O((V+E)logV)를 가진다.
import java.io.*;
import java.util.*;
class Town implements Comparable<Town>{
int to;
int cost;
public Town(int to, int cost) {
this.to = to;
this.cost = cost;
}
@Override
public int compareTo(Town o) {
return this.cost - o.cost;
}
}
public class Main {
static int n,m,x;
static List<Town>[] nList;
static List<Town>[] rList;
static int INF = 1_000_000_000;
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());
m = Integer.parseInt(st.nextToken());
x = Integer.parseInt(st.nextToken());
nList = new ArrayList[n+1];
rList = new ArrayList[n+1];
for(int i=0; i<n+1; i++) {
nList[i] = new ArrayList<>();
rList[i] = new ArrayList<>();
}
for(int i=0; i<m; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
int cost = Integer.parseInt(st.nextToken());
nList[from].add(new Town(to, cost));
rList[to].add(new Town(from, cost));
}
// 다른 모든 마을 -> X 마을 거리
int[] go = dijkstra(nList, x);
// X 마을 -> 다른 모든 마을
int[] back = dijkstra(rList, x);
int res = Integer.MIN_VALUE;
for(int i=1; i<n+1; i++) {
int dis = go[i] + back[i];
if(dis > res) {
res = dis;
}
}
System.out.println(res);
}
static int[] dijkstra(List<Town>[] list, int start) {
Queue<Town> q = new PriorityQueue<>();
boolean[] check = new boolean[n+1];
int[] dp = new int[n+1];
Arrays.fill(dp, INF);
q.add(new Town(start, 0));
dp[start]=0;
while(!q.isEmpty()) {
Town pos = q.poll();
int to = pos.to;
if(check[to]) continue;
check[to] = true;
for(Town next : list[to]) {
if(dp[to] + next.cost < dp[next.to]) {
dp[next.to] = dp[to] + next.cost;
q.add(new Town(next.to, dp[next.to]));
}
}
}
return dp;
}
}
실행결과
역시 예상대로 다익스트라 알고리즘이 효율성이 높은 것을 알 수 있다. 걸리는 시간의 차이가 무려 10배정도 플로이드 와샬 알고리즘이 느리다.
'Dot Algo∙ DS > PS' 카테고리의 다른 글
| [BOJ] 백준 5014번 스타트링크 (Java) (0) | 2021.05.20 |
|---|---|
| [BOJ] 백준 11062번 카드 게임 (Java) (0) | 2021.05.20 |
| [BOJ] 백준 10451번 순열 사이클 (Java) (0) | 2021.05.18 |
| [BOJ] 백준 1328번 고층 빌딩 (Java) (0) | 2021.05.17 |
| [BOJ] 백준 3344번 N-Queen (백트래킹x) (JAVA) (0) | 2021.05.17 |
