백준 군사 이동(11085)
1. 힌트
1) 가장 좁은 길의 너비를 최대화하는 것이므로 실제 경로가 얼마나 많은 정점을 거치는가는 상관 없습니다.
2) 가장 너비가 큰 간선부터 골라서 그래프를 구성해봅시다. 그러다가 만약 와 가 한 컴포넌트에 속하게 된다면 그때 추가한 간선이 문제의 정답입니다.
3) 두 정점이 서로 같은 컴포넌트인지 빠르게 확인하기 위해 Union Find 자료 구조를 사용할 수 있습니다.
2. 접근
1) 최단경로가 아닙니다.
간선의 가중치가 주어지고 사이의 최단 경로라면 다익스트라로 쉽게 구할 수 있습니다. 그런데 이 문제에서 요구하는 것은 조금 특이합니다. 얼마나 많은 정점을 거쳤건 간에 그 경로에서 가장 좁은 간선이 가장 넓다는 것입니다.
2) 가장 큰 간선부터 선택해보자.
최단 경로가 아니므로 가장 큰 간선부터 선택해나가면서 그래프를 만들어봅시다. 그래프가 하나가 아닐 수도 있고 사이클이 있을 수도 있지만, 우리는 가 이동 가능한지만 확인하면 됩니다. 이동할 수 있다면 경로상에서 가장 작은 길의 가중치는 방금 막 선택한 간선이 될 것입니다.
3) Union Find
두 정점이 같은 컴포넌트에 속하는지 여부는 Union Find자료구조를 사용하면 의 시간에 알아낼 수 있습니다. 이렇게 하면 정렬하는데 필요한 의 시간만에 확인할 수 있습니다.
4) 파라메트릭 서치 풀이
다른 풀이도 있습니다. 보통 가장 작은(큰) ~~을 최대화(최소화)를 하라는 말이 나오면 파라메트릭 서치(이분 탐색)을 먼저 생각하곤 합니다. 우리는 판정함수 를 다음과 같이 정의할 수 있습니다
경로 상에 가장 작은 간선의 크기가 이상이 되도록 이동 가능한지 여부
가 참이라면 도 참이므로 주어진 함수 는 이분 탐색이 가능합니다.
3. 구현
public class Main {
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());
st = new StringTokenizer(br.readLine(), " ");
int A = Integer.parseInt(st.nextToken());
int B = Integer.parseInt(st.nextToken());
ArrayList<Edge> S = new ArrayList<>(M);
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine(), " ");
int u = Integer.parseInt(st.nextToken());
int v = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
S.add(new Edge(u, v, w));
S.add(new Edge(v, u, w));
}
Collections.sort(S);
DisjointSet set = new DisjointSet(N);
int ret = 0;
for (Edge e : S) {
int u = e.start; int v = e.end; int w = e.weight;
set.union(u, v);
if (set.find(A) == set.find(B)) {
ret = w; break;
}
}
System.out.println(ret);
}
}
class DisjointSet {
int[] parent; int[] rank;
public DisjointSet(int n) {
parent = new int[n]; for (int i = 0; i < n; i++) parent[i] = i;
rank = new int[n];
}
void union(int u, int v) {
u = find(u); v = find(v);
if (u == v) return;
if (rank[u] > rank[v]) { int temp = u; u = v; v = temp; }
parent[u] = v;
if (rank[u] == rank[v]) rank[v]++;
}
int find(int u) {
if (parent[u] == u) return u;
return parent[u] = find(parent[u]);
}
}
class Edge implements Comparable<Edge> {
int start, end, weight;
public Edge(int s, int e, int w) { start = s; end = e; weight = w; }
@Override
public int compareTo(Edge o) { return o.weight - weight; }
}
1) 시간 복잡도
Author And Source
이 문제에 관하여(백준 군사 이동(11085)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@axiom0510/b11085저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)