문제 링크

성능 요약

메모리: 49464 KB, 시간: 500 ms

분류

너비 우선 탐색, 이분 탐색, 자료 구조, 분리 집합, 그래프 이론, 그래프 탐색, 최단 경로

제출 일자

2025년 2월 14일 21:11:11

문제 설명

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인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

풀이

느낀점

• 매개변수 이분탐색으로도 풀 수 있을 것 같긴 했는데 느낌상 크루스칼이 더 빠를것 같았다.

설계 : 10분

• 크루스칼은 간선을 기준으로 가중치가 적은 것부터 사용하면서 findSet/unionSet 을 사용하는 방식이다.
• 이 문제에서는 두 공장이 연결되기까지 가장 중량을 많이 견딜 수 있는 다리들만 사용해야 한다.
• 따라서 중량제한 기준 내림차순으로 간선들을 정렬한 후 순회하여 두 공장이 연결되는 순간 사용한 간선의 중량제한을 답으로 처리했다.

코드(Java)

• 구현 시간: 15분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 중량제한_1939
 * Date: 2025.02.14
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;
    static int[] p;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));

		String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);

        List<Edge> edges = new ArrayList<>();
        for (int i = 0 ; i < m; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());

            edges.add(new Edge(start, end, weight));
        }
        Collections.sort(edges);

        st = new StringTokenizer(br.readLine(), " ");
        int fac1 = Integer.parseInt(st.nextToken());
        int fac2 = Integer.parseInt(st.nextToken());

        p = new int[n+1];
        for (int i = 1; i <= n; i++) p[i] = i;

        for (int i = 0; i < m; i++) {
            Edge edge = edges.get(i);

            int a = findSet(edge.start);
            int b = findSet(edge.end);

            if (a != b) p[a] = b;

            if (findSet(fac1) == findSet(fac2)) {
                bw.write(String.valueOf(edge.w));
                break;
            }
        }

		bw.flush();
		bw.close();
		br.close();
	}
    public static int findSet(int x) {
        if (p[x] == x) return x;
        return p[x] = findSet(p[x]);
    }
}

class Edge implements Comparable<Edge> {
    int start;
    int end;
    int w;

    Edge (int start, int end, int w) {
        this.start = start;
        this.end = end;
        this.w = w;
    }

    @Override
    public int compareTo(Edge o) {
        return Integer.compare(o.w, this.w);
    }
}