백준 군사 이동(11085)

군사 이동

1. 힌트

1) 가장 좁은 길의 너비를 최대화하는 것이므로 실제 경로가 얼마나 많은 정점을 거치는가는 상관 없습니다.

2) 가장 너비가 큰 간선부터 골라서 그래프를 구성해봅시다. 그러다가 만약 $c$와 $v$가 한 컴포넌트에 속하게 된다면 그때 추가한 간선이 문제의 정답입니다.

3) 두 정점이 서로 같은 컴포넌트인지 빠르게 확인하기 위해 Union Find 자료 구조를 사용할 수 있습니다.

2. 접근

1) 최단경로가 아닙니다.

간선의 가중치가 주어지고 $(c, v)$사이의 최단 경로라면 다익스트라로 쉽게 구할 수 있습니다. 그런데 이 문제에서 요구하는 것은 조금 특이합니다. 얼마나 많은 정점을 거쳤건 간에 그 경로에서 가장 좁은 간선이 가장 넓다는 것입니다.

2) 가장 큰 간선부터 선택해보자.

최단 경로가 아니므로 가장 큰 간선부터 선택해나가면서 그래프를 만들어봅시다. 그래프가 하나가 아닐 수도 있고 사이클이 있을 수도 있지만, 우리는 $(c,v)$가 이동 가능한지만 확인하면 됩니다. 이동할 수 있다면 경로상에서 가장 작은 길의 가중치는 방금 막 선택한 간선이 될 것입니다.

3) Union Find

두 정점이 같은 컴포넌트에 속하는지 여부는 Union Find자료구조를 사용하면 $O(1)$의 시간에 알아낼 수 있습니다. 이렇게 하면 정렬하는데 필요한 $O(NlgN)$의 시간만에 확인할 수 있습니다.

4) 파라메트릭 서치 풀이

다른 풀이도 있습니다. 보통 가장 작은(큰) ~~을 최대화(최소화)를 하라는 말이 나오면 파라메트릭 서치(이분 탐색)을 먼저 생각하곤 합니다. 우리는 판정함수 $f$를 다음과 같이 정의할 수 있습니다
$f(x) =$ 경로 상에 가장 작은 간선의 크기가 $x$이상이 되도록 $(c, v)$이동 가능한지 여부

$f(x)$가 참이라면 $f(x - 1)$

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) 시간 복잡도

$O(NlgN)$