백준 2350 - 대운하

문제

https://www.acmicpc.net/problem/2350

풀이

문제의 조건을 살펴보면, 정점 $i$에서 $j$까지의 경로가 존재할 때 경로에 존재하는
가장 폭이 작은 간선의 폭을 최대화해야 한다.(그래야 배의 폭을 최대화할 수 있다)

이 조건을 실현하기 위해 크루스칼을 활용해 그래프내 포함된 간선의 폭을 최대화하는
방향으로 MST를 만들었다. 로직은 다음 과정을 걸쳐 전개된다.
1. 간선 정보를 저장하는 클래스, Edge정의. 폭 기준 최대힙에 간선 저장
2. 유니온-파인드 연산을 활용해 N-1개의 간선을 채택하여 폭이 최대화된 형태의 MST 생성
3. MST를 형성하며 그래프로 표현, getMaxWidth() 로직은 경로 시작점과 끝점을 전달 받아 preNode 2차원 배열에 경로상 직전 노드, 비용을 저장. 해당 값을 바탕으로 직전 노드를 추적하며 경로상 가능한 최대 폭을 도출

로직의 시간복잡도는 MST를 생성하는 과정에서 $O(MlogM)$, $K$개의 쿼리를 처리하는데
$O(K(N-1))$이 소요되며 $N, M, K$가 최대일 때도 무난히 제한 조건 통과.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.IntStream;

import static java.lang.Integer.*;

public class Main {
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = parseInt(st.nextToken());
        int M = parseInt(st.nextToken());
        int K = parseInt(st.nextToken());

        parent = new int[N + 1];
        Arrays.fill(parent, -1);

        PriorityQueue<Edge> pq = new PriorityQueue<>((e1, e2) -> Integer.compare(e2.w, e1.w));
        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int u = parseInt(st.nextToken());
            int v = parseInt(st.nextToken());
            int w = parseInt(st.nextToken());

            pq.add(new Edge(u, v, w));
        }

        List<List<Node>> graph = new ArrayList<>();
        IntStream.range(0, N + 1).forEach(i -> graph.add(new ArrayList<>()));

        int count = 0;
        while (count < N - 1) {
            Edge e = pq.poll();

            int p1 = find(e.u);
            int p2 = find(e.v);

            if (p1 == p2) {
                continue;
            }

            if (parent[p1] < parent[p2]) {
                parent[p2] += parent[p1];
                parent[p1] = p2;
            } else {
                parent[p1] += parent[p2];
                parent[p2] = p1;
            }

            graph.get(e.u).add(new Node(e.v, e.w));
            graph.get(e.v).add(new Node(e.u, e.w));
            count++;
        }

        StringBuilder sb = new StringBuilder();
        while (K-- > 0) {
            st = new StringTokenizer(br.readLine());
            int i = parseInt(st.nextToken());
            int j = parseInt(st.nextToken());
            sb.append(getMaxWidth(i, j, graph)).append("\n");
        }

        System.out.println(sb);
        br.close();
    }

    static int find(int u) {
        if (parent[u] < 0) return u;

        return parent[u] = find(parent[u]);
    }

    static int getMaxWidth(int start, int end, List<List<Node>> graph) {
        int[][] preNode = new int[2][graph.size()];
        Arrays.fill(preNode[0], -1);

        ArrayDeque<Integer> queue = new ArrayDeque<>();
        queue.add(start);

        int cur;

        while (!queue.isEmpty()) {
            cur = queue.poll();
            if (cur == end) break;

            for (Node next : graph.get(cur)) {
                if (preNode[0][next.v] != -1) continue;

                preNode[0][next.v] = cur;
                preNode[1][next.v] = next.w;
                queue.add(next.v);
            }
        }

        cur = end;
        int maxWidth = MAX_VALUE;
        while (cur != start) {
            maxWidth = Math.min(maxWidth, preNode[1][cur]);
            cur = preNode[0][cur];
        }

        return maxWidth;
    }

    static class Edge {
        int u, v, w;

        public Edge(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }
    }

    static class Node {
        int v, w;

        public Node(int v, int w) {
            this.v = v;
            this.w = w;
        }
    }
}

결과