백준 1939 풀이
중량제한
https://www.acmicpc.net/problem/1939
풀이
중량 제한이 있고 진행하는 경로 상에서는 가장 작은 중량 제한을 가지는 간선을 선택해야 하고 경로를 결정하는 것에는 중량 제한이 큰 간선들을 선택해야 한다.
그러기 위해 MST를 변형한 최대 신장 트리를 이용해서 풀이한다.
최소 신장 트리는 비용이 작은 간선부터 선택을 하여 트리를 만든다면 최대 신장 트리는 비용이 큰 간선부터 선택을 하여 트리를 만든다.
이렇게 하면 앞서 생각했던 내용들을 구현할 수 있다. 비용이 큰 경로만을 선택하여 만들어진 경로이고 이 때 가장 작은 비용이 문제의 답이 된다.
코드
import java.io.*;
import java.util.PriorityQueue;
public class Main {
static int[] dx = {-1, 0, 0, 1};
static int[] dy = {0, -1, 1, 0};
static int n, m;
static PriorityQueue<Edge> priorityQueue;
static int[] p;
static int[] rank;
public static void main(String[] args) throws IOException {
// write your code here
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] input = br.readLine().split(" ");
n = Integer.parseInt(input[0]);
m = Integer.parseInt(input[1]);
priorityQueue = new PriorityQueue<>();
p = new int[n + 1];
rank = new int[n + 1];
for (int i = 0; i <= n; i++) {
p[i] = i;
rank[i] = 1;
}
for (int i = 0; i < m; i++) {
String[] line = br.readLine().split(" ");
int x = Integer.parseInt(line[0]);
int y = Integer.parseInt(line[1]);
int w = Integer.parseInt(line[2]);
priorityQueue.add(new Edge(x, y, w));
//bw.write(count + "\n");
}
String[] last = br.readLine().split(" ");
int src = Integer.parseInt(last[0]);
int dest = Integer.parseInt(last[1]);
int ans = mst(src, dest);
bw.write(ans + "\n");
bw.close();
br.close();
}
private static int mst(int src, int dest) {
while (!priorityQueue.isEmpty()) {
Edge e = priorityQueue.poll();
int x = e.x;
int y = e.y;
union(x, y);
if (find(src) == find(dest))
return e.w;
}
return -1;
}
private static int union(int a, int b) {
int ar = find(a);
int br = find(b);
if (ar != br) {
if (rank[ar] < rank[br])
p[ar] = br;
else {
p[br] = ar;
if (rank[ar] == rank[br]) {
rank[ar]++;
}
}
}
return rank[ar];
}
private static int find(int a) {
if (a == p[a])
return a;
else {
int y = find(p[a]);
p[a] = y;
return y;
}
}
}
class Edge implements Comparable<Edge> {
public int x;
public int y;
public int w;
public Edge(int x, int y, int w) {
this.x = x;
this.y = y;
this.w = w;
}
@Override
public int compareTo(Edge o) {
return Integer.compare(o.w, this.w);
}
}
추가
추가로 이분탐색+bfs로 풀이할 수 있는데 이 방법은 추후 정리해서 추가할 예정이다.
Author And Source
이 문제에 관하여(백준 1939 풀이), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@estry/백준-1939-풀이저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)