[ BOJ ][JAVA][1939] 중량제한

www.acmicpc.net/problem/1939

1939번: 중량제한

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	17096	4271	2629	24.395%

문제

N(2≤N≤10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

3 3
1 2 2
3 1 3
2 3 2
1 3

예제 출력 1

3

코드

크루스칼 알고리즘 풀이

/*
    중량제한
    1. 최대 스패닝 트리
        -> 최소 스패닝 트리의 반대 버전으로, 가중치가 가장 큰 간선을 선택하면서 스패닝 트리를 만들ㅇ 너간다.
        -> 그러면 어떤 정점S  와 다른정점 E 가 같은 집합에 속하는 순간 우리가 원하는 경로가 완성된다.
        -> 이렇게 완성된 경로는 최장경로 처럼, 가능하면 무거운 짐을 옮길 수 있는 다리만 선택하여 만들어진 것
    2. 이분탐색 + BFS
*/
import java.io.*;
import java.util.*;
public class p1939 {
    static class Edge implements Comparable<Edge> {
        int u, v, cost;
        public Edge(int u, int v, int cost) {
            this.u = u;
            this.v = v;
            this.cost = cost;
        }

        public int compareTo(Edge o) {
            return o.cost - cost;
        }
    }
    static int n, m, s, e;
    static PriorityQueue<Edge> pq;
    static int[] parent, rank;
    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());
        pq = new PriorityQueue<>();
        parent = new int[n + 1];
        rank = new int [n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }

        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 cost = Integer.parseInt(st.nextToken());
            pq.add(new Edge(u, v, cost));
        }

        st = new StringTokenizer(br.readLine());
        s = Integer.parseInt(st.nextToken());
        e = Integer.parseInt(st.nextToken());

        System.out.println(mst());
    }

    static int mst() {
        while (!pq.isEmpty()) {
            Edge edge = pq.poll();
            int u = edge.u;
            int v = edge.v;
            union(u, v);
            if (find(s) == find(e)) return edge.cost;
        }

        return -1;
    }

    static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) {
            if (rank[a] < rank[b]) {
                parent[a] = b;
            } else {
                parent[b] = a;
                if (rank[a] == rank[b]) {
                    rank[a]++;
                }
            }
        }
    }

    static int find(int x) {
        if (x == parent[x]) return x;

        return find(parent[x]);
    }
}

BFS + 이분탐색 풀이

/*
    중량제한
*/
import java.io.*;
import java.util.*;

public class p1939 {
    static class Node {
        int to;
        long cost;
        public Node (int to, long cost) {
            this.to = to;
            this.cost = cost;
        }
    }
    static final int INF = 987654321;
    static int n, m, max = 0;
    static long[] dist;
    static boolean[] visited;
    static List<Node>[] list;
    static Queue<Integer> q;
    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());
        visited = new boolean[n + 1];
        list = new ArrayList[n + 1];
        q = new LinkedList<>();
        for (int i = 0; i <= n; i++) {
            list[i] = new ArrayList<>();
        }
        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 cost = Integer.parseInt(st.nextToken());
            list[u].add(new Node(v, cost));
            list[v].add(new Node(u, cost));
            max = Math.max(max, cost);
        }

        st = new StringTokenizer(br.readLine());
        int s = Integer.parseInt(st.nextToken());
        int e = Integer.parseInt(st.nextToken());

        long ret = binarySearch(s, e);

        System.out.println(ret);
    }

    static long binarySearch(int from, int to) {
        long left = 1, right = max;
        long mid = 0, ans = 0;
        while (left <= right) {
            mid = (left + right) / 2;

            if (go (from, to, mid)) {
                ans = mid > ans ? mid : ans;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return ans;
    }

    static boolean go (int from, int to, long weight) {
        clear();

        q.offer(from);
        visited[from] = true;

        while (!q.isEmpty()) {
            int cur = q.poll();

            if (cur == to) {
                return true;
            }

            for (Node next : list[cur]) {
                if (visited[next.to]) continue;
                if (weight <= next.cost) {
                    q.offer(next.to);
                    visited[next.to] = true;
                }
            }
        }

        return false;
    }

    static void clear() {
        q.clear();

        Arrays.fill(visited, false);
    }
}