[백준 Gold 4] 1939 중량제한 - Java

문제링크 : https://www.acmicpc.net/problem/1939

1939번: 중량제한

 

접근 과정 : 

• 주어지는 두 섬 A,B를 연결하는 많은 경로 중에서, 이동할 수 있는 중량이 최대인 것을 출력하면 된다.
• 경로를 진행할 때, 최종적으로 옮길 수 있는 중량은 지나온 다리들의 최소 중량 제한이다.
• 처음에는 DFS로 경로를 진행하고, 중량을 산출하려고 했다.
• 갱신된 Answer 값과 현재 진행중인 경로의 중량을 비교해서 DFS 연산을 최소화시키려고 했다.
• 그런데!!! 시간초과가 나오더라.
• DFS나 BFS를 사용하려면, 확인하려는 중량으로 이분탐색하고 가능한 경로인지 확인해야 하는 것 같다.

+++ 근데!! 난 이게 먼가 최악의 엣지 케이스만을 방지하는 것 같고,

그렇게 큰 차이가 나올것 같지 않다는 생각이 들었다.

• 그래서 크루스칼 알고리즘을 활용해서 가장 중량이 큰 다리부터 진행했다.
• 그리고 연결 그룹을 확인하면서 A,B가 연결되었는지 체크했다.
• 연결되었다면, 그 순간 중량이 결과값이다!!

 

소스 코드 및 결과 :

 

package BOJ;

/* 
    중량제한
*/

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

public class BOJ1539 {

    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());

        List<int[]> bridge = new ArrayList<>();

        while (M-- > 0) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            bridge.add(new int[] { A, B, C });

        }

        st = new StringTokenizer(br.readLine());
        int from = Integer.parseInt(st.nextToken());
        int to = Integer.parseInt(st.nextToken());

        Collections.sort(bridge, (a, b) -> {
            return b[2] - a[2];
        });

        root = new int[N+1];

        for (int[] b : bridge) {

            int x = findRoot(b[0]);
            int y = findRoot(b[1]);
            if (x== y) {
                continue;
            }

            root[y] = x;

            if(findRoot(from) == findRoot(to)){
                System.out.println(b[2]);
                break;
            }
        }
    }

    static int[] root;

    static int findRoot(int x) {
        if (root[x] == 0) {
            return x;
        }

        return root[x] = findRoot(root[x]);
    }

}

 

P.S 

문제를 해결하지 못한다고 해도, 다른 이의 해결법이나 문제가 제시하는 방향을 그대로 따라하는 것은 선호하지 않는다.

모든 문제 유형 - 풀이 방식을 외울 수는 없다..

 

그래서 만약에 내가 다음에 이러한 유형을 접했을 때, 내가 접근 하는 방식을 고려해서 해결하려고 한다.

이번 문제가 그런 문제가 아니었나 싶다..

나는 아마 다음에 이런 유형을 접해도, BFS/DFS 에 이분탐색을 결합해서 풀지는 않을 것 같더라..