백준 1939번 : 중량제한 [자바]

 

 

 

🧫 문제 분석

 

✔️ 출처

중량제한 골드 3

 

📖 문제

 

최단 경로 + 최대신장(최소 신장의 반대라서 이렇게 붙였다) + 이분탐색 문제다.

근데 본인은 최대 신장 트리로 안풀고, 현재 이분탐색 문제를 공부중이므로 이분탐색 + BFS 최단경로로 풀었다. 

 

이분탐색으로 찾고자 하는 것은 두 섬 사이의 경로 이동 비용 최댓값이다. 

가장 비용이 큰 값을 max로 잡고 

1 ~ max 사이를 이분탐색하면서 mid값으로 BFS 탐색을 한다.

 

BFS 탐색에서는 공장이 있는 섬A에서부터 탐색을 하되 mid 값 (중량)을 다리의 중량제한이 버틸 수 있다면 다음 다리로 탐색한다. 

공장이 있는 섬 B에 도착하면 현재 mid 값의 중량은 버틴다는 의미이므로 true를 반환해 알린다.

이분탐색에서는 BFS 결과가 true이면 mid 값을 더 키워서 최대 중량값을 찾는다. 

 

 

최대신장트리로 푸는 방법

크루스칼 알고리즘을 이용한다. 

공장이 있는 각 섬의 부모가 같다면 그때 연결한 섬의 비용이 최대 비용이라고 볼 수 있다. 

 - 비용 내림차순 정렬을 했고, 큰 비용부터 하나씩 최대 비용 간선을 연결한다.

-  연결하면서 공장이 있는 각 섬의 부모를 체크해서 두 섬의 부모가 같다면 현재 연결한 간선의 비용이 무게 최댓값인데

-  이이상 더 큰 값이 최댓값일 수가 없다. 그 뒤에 연결하는 간선들의 비용은 내림차순이기에 점점 줄어들기 떄문이다. 

 

 

---

🔅 문제 풀이

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

public class Main {

    static class Island {
        int next;
        int cost;
        public Island (int next, int cost) {
            this.next = next;
            this.cost = cost;
        }
    }
    
    static ArrayList<Island>[] graph;
    static boolean[] visited;
    static int max = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 섬 개수
        int m = Integer.parseInt(st.nextToken()); // 다리 개수

        graph = new ArrayList[n + 1];
        visited = new boolean[n + 1];

        // 섬 그래프로 초기화
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken()); // 섬1
            int B = Integer.parseInt(st.nextToken()); // 섬2
            int C = Integer.parseInt(st.nextToken()); // 비용

            if (graph[A] == null) graph[A] = new ArrayList<>();
            if (graph[B] == null) graph[B] = new ArrayList<>();
            graph[A].add(new Island(B, C));
            graph[B].add(new Island(A, C));
            max = Math.max(max, C); // 탐색 범위 max 값
        }

        // 비용 내림차순 정렬
        for (ArrayList<Island> list : graph) {
            if (list != null) {
                Collections.sort(list, (o1, o2) -> o2.cost - o1.cost);
            }
        }

        // 공장이 있는 두 섬
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());


		// 비용 이분탐색
        int front = 1, back = max;
        int max = 0;
        while (front <= back) {

            int mid = (front + back) >>> 1;

            if (bfs(start, end, mid)) {
                front = mid + 1;
                max = mid;
            } else {
                back = mid - 1;
            }

            visited = new boolean[n + 1];
        }

        System.out.println(max);

    }

    // bfs로 공장이 있는 A -> B로 가는 길에 mid값으로 갈 수 있는 지 확인
    private static boolean bfs(int start, int end, int cost) {
        Queue<Island> q = new LinkedList<>();
        q.add(new Island(start, 0));
        visited[start] = true;

        while (!q.isEmpty()) {
            Island curIsland = q.poll();
            
            // 반대편 공장이 있는 섬에 도착했다면 true 반환
            if (curIsland.next == end) {
                return true;
            }

            ArrayList<Island> list = graph[curIsland.next];
            for (int i = 0; i < list.size(); i++) {

                Island nextIsland = list.get(i);
                // 방문하지 않았으면서, cost로 이동 가능하면 큐에 추가
                if (!visited[nextIsland.next] && nextIsland.cost >= cost) {
                    q.add(nextIsland);

                    visited[nextIsland.next] = true;
                }
            }
        }

        return false;
    }

}

 

 

🔅 크루스칼 알고리즘 풀이

import java.io.*;
import java.util.*;
import java.util.stream.IntStream;

public class Main {


    static int[][] graph;
    static int[] parent;
    static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
//        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken()); // 섬 개수
        int m = Integer.parseInt(st.nextToken()); // 다리 개수

        graph = new int [m][3];
        parent = IntStream.range(0, n + 1).toArray(); // 부모

        // 섬 그래프로 초기화
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            graph[i][0] = Integer.parseInt(st.nextToken()); // 섬1
            graph[i][1] = Integer.parseInt(st.nextToken()); // 섬2
            graph[i][2] = Integer.parseInt(st.nextToken()); // 비용
        }
        st = new StringTokenizer(br.readLine());
        int start = Integer.parseInt(st.nextToken());
        int end = Integer.parseInt(st.nextToken());

        // 비용 내림차순 정렬
        Arrays.sort(graph, (o1, o2) -> o2[2] - o1[2]);

        for (int i = 0; i < m; i++) {
            if (find(graph[i][0]) != find(graph[i][1])) { // 서로 다른 부모 즉, 사이클이 생기지 않는다면
                union(graph[i][0], graph[i][1]);
                if (find(parent[start]) == find(parent[end])) { // 시작과 끝점의 부모가 같다면 현재 비용이 이동가능한 무게 최댓값
                    min = graph[i][2];
                    break;
                }
            }
        }

        System.out.println(min);
    }
    private static void union(int a, int b) {
        a = find(a);
        b = find(b);

        if (a > b) {
            parent[a] = b;
        } else {
            parent[b] = a;
        }
    }

    private static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]); // 경로압축
    }
}

 

❗ 오답노트 / 필요한 지식

1.