Algorithm
Spanning Tree 문제 - 알고스팟 여행 경로 정하기
VNAROOOD
2019. 9. 23. 22:10
문제 출처: 알고스팟
https://algospot.com/judge/problem/read/TPATH
algospot.com :: TPATH
여행 경로 정하기 문제 정보 문제 당신은 철도망을 이용해 한 도시에서 다른 도시까지 여행을 하고 싶다. 철도망은 여러 개의 역들과 그들을 잇는 노선으로 구성되어 있다. 각 구간별로 철도의 운행 속도가 정해져 있다. 당신은 멀미를 심하기 하는 편이라, 철도가 가속과 감속을 반복하면 매우 괴롭다. 따라서, 가능한한 여행 중에는 항상 비슷한 속도로 여행하고 싶어한다. 철도망이 주어질 때, 여행 구간 중 최대 운행 속도와 최소 운행 속도의 차를 최소화하는 경로를
algospot.com
가중치의 최소값을 구하는 최소 스패닝 트리 문제와 달리,
해당 문제는 경로 중 가중치의 최소값과 최대값 오차를 적게 하는 것이 포인트이다.
아래 소스는 크루스칼 기본 소스이다.
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
public class _20190923_여행경로 {
// 2) 구간 생성
static List<Rail0923> rail;
// 4) Union-find
static int parent[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
int C = Integer.parseInt(br.readLine());
for (int TestCase = 1; TestCase <= C; TestCase++) {
st = new StringTokenizer(br.readLine());
// 1) 철도역 N, 운행구간 M
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
// 2) 간선생성
rail = new ArrayList<Rail0923>();
// 4) Union-find
parent = new int[N];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
// 1) 운행 구간 정보
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
rail.add(new Rail0923(a, b, c));
}
// 3) 가중치순 오름차순 정렬
Collections.sort(rail, new Comparator<Rail0923>() {
@Override
public int compare(Rail0923 o1, Rail0923 o2) {
return o1.c < o2.c ? -1 : 1;
}
});
// 5) 가중치 순으로 돌리기
int answer = 0;
for (int i = idx; i < M; i++) {
if (find(0) == find(N-1)) {
break;
}
int sp = rail.get(i).a;
int ep = rail.get(i).b;
if (find(sp) == find(ep)) continue;
union(sp, ep);
answer += rail.get(i).c;
}
sb.append(answer);
sb.append("\n");
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
bw.write(sb.toString());
bw.flush();
}
// 4) Union-find
static void init(){
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
}
static int find(int x){
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
static void union(int a, int b){
int pa = parent[a];
int pb = parent[b];
if (pa == pb) return;
parent[pb] = pa;
}
// End of Union-find
}
class Rail0923 {
int a;
int b;
int c;
public Rail0923(int a, int b, int c) {
super();
this.a = a;
this.b = b;
this.c = c;
}
}
그러나 최소 경로는 위 코드만으로 해결되지 않는다.
가중치 최대값과 최소값의 차이가 최소인 값을 찾아야하는데, 최대값과 최소값을 어떻게 찾을까?
최대값과 최소값을 각각 찾기보다는 다른 방식으로 접근해야 한다.
MST를 통해 값을 찾았다면, 최대값과 최소값의 차이를 구한 셈이다.
그렇다면 최소값을 하나씩 증가시키며, MST를 만들어내는지를 보면 된다.
즉
1. 오름차순으로 정렬한 목록에서 간선을 하나씩 제외하며 MST를 만들어내는지를 확인한다.
또한
2. 간선을 하나씩 제하던 중 MST를 만드는데에 실패했다면, 더이상 MST를 만들 수 없다고 판단하고 추가로 찾지 않도록 한다.
=> 시간초과를 방지하기 위함
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
public class _20190923_여행경로 {
// 2) 구간 생성
static List<Rail0923> rail;
// 4) Union-find
static int parent[];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
int C = Integer.parseInt(br.readLine());
for (int TestCase = 1; TestCase <= C; TestCase++) {
st = new StringTokenizer(br.readLine());
// 1) 철도역 N, 운행구간 M
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
// 2) 간선생성
rail = new ArrayList<Rail0923>();
// 4) Union-find
parent = new int[N];
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
// 1) 운행 구간 정보
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
rail.add(new Rail0923(a, b, c));
}
// 3) 가중치순 오름차순 정렬
Collections.sort(rail, new Comparator<Rail0923>() {
@Override
public int compare(Rail0923 o1, Rail0923 o2) {
return o1.c < o2.c ? -1 : 1;
}
});
// 최대값과 최소값의 차
int gap = Integer.MAX_VALUE;
for (int idx = 0; idx < M; idx++) { // MST를 여러 번 수행하기 위한 루
int min = Integer.MAX_VALUE; // idx번째 MST에서 최소값
int max = Integer.MIN_VALUE; // idx번째 MST에서 최대값
// Union-find 초기화
init();
// 5) 가중치 순으로 돌리기
// 이때, 최소값 간선을 제외하며 돌리므로 i는 idx부터 시작한다.
for (int i = idx; i < M; i++) {
if (find(0) == find(N-1)) {
gap = min(gap, max - min);
break;
}
int sp = rail.get(i).a;
int ep = rail.get(i).b;
if (find(sp) == find(ep)) continue;
min = min(min, rail.get(i).c); // idx번째 MST에서 최소값 갱신
max = max(max, rail.get(i).c); // idx번째 MST에서 최대값 갱신
union(sp, ep);
}
if(find(0) == find(N-1)){
// idx번째 MST 가 MST를 이룬다면, gap을 계산해둔다
gap = min(gap, max - min);
}else{
// idx번째 MST가 MST를 이루지 못한다면, 더이상 MST를 검색하는 것을 중단한다.
break;
}
}
sb.append(gap);
sb.append("\n");
}
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
bw.write(sb.toString());
bw.flush();
}
static int min(int a, int b){return a<b?a:b;}
static int max(int a, int b){return a>b?a:b;}
// 4) Union-find
static void init(){
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
}
static int find(int x){
if (parent[x] == x) return x;
return parent[x] = find(parent[x]);
}
static void union(int a, int b){
int pa = parent[a];
int pb = parent[b];
if (pa == pb) return;
parent[pb] = pa;
}
// End of Union-find
}
class Rail0923 {
int a;
int b;
int c;
public Rail0923(int a, int b, int c) {
super();
this.a = a;
this.b = b;
this.c = c;
}
}