BOJ 1939 중량제한 [Java]

BOJ 1939 중량제한

1. 문제 링크

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

2. 문제 해설

처음에는 실수로 시간복잡도를 생각 안하고 접근했다. 공장이 있는 섬 두 개 중 한 지점에서 다른 지점까지 갈 수 있는 모든 경로를 살펴보면서 각 경로마다의 최소의 중량제한을 구하고, 그 값의 최대값을 구하는 방식을 dfs로 구현하였다. 시간복잡도가 O(NM)으로 당연히 시간초과가 나왔다.
시간복잡도를 줄일 수 있는 방법이 무엇이 있을까 고민하다가, 각 다리의 중량제한의 범위가 1 ≤ C ≤ 1,000,000,000 으로 굉장히 큰 것을 보고 이분탐색을 떠올렸다. BFS와 이분탐색을 이용해서 풀 수 있는데, 각 로직의 흐름을 설명해보겠다.

• 이분탐색 로직
  이분탐색을 할 대상은 물품의 중량이다. 각 다리의 중량제한의 범위가 1 ≤ C ≤ 1,000,000,000 이므로 옮겨야할 물품의 중량의 범위도 같다. 물품의 중량을 x 라고 했을 때, BFS를 통해서 그 물품을 옮길 수 있는지 판단한다. 만약 옮길 수 있다면 물품의 중량은 더 커질 수 있는 것이므로 lo = mid 로 처리해준다. 옮길 수 없다면 물품의 중량 범위를 낮춰야하므로 hi = mid 로 처리한다.
  이분탐색이 헷갈린다면 아래 글을 보자.
  https://jun-codinghistory.tistory.com/154?category=1006180

• BFS 로직
  옮겨야할 물품의 중량이 x라고 하자. 평범한 BFS 로직이지만 추가해야할 것이 있다면, 경로를 탐색하는데 다음 섬을 가기 위한 다리의 중량제한이 현재 옮기고자 하는 물품의 중량보다 작다면 갈 필요가 없다는 점만 고려해주면 된다.
  그리고 추가로 주의할 점이 있다면 섬을 그래프로 구현할 때, 섬의 최대 갯수가 10000개 이므로 인접행렬로 구현하면 안된다. 인접리스트 방식으로 구현해주도록 하자.

3. 코드 보기

시간초과가 나온 DFS 코드

import java.io.*;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static class Bridge {
        int num, weight;

        public Bridge(int num, int weight) {
            this.num = num;
            this.weight = weight;
        }
    }

    static int n, m;
    static ArrayList<ArrayList<Bridge>> adj;
    static boolean[] vis;
    static int[] minWeight;
    static int fac1, fac2;
    static int answer = Integer.MIN_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());

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        adj = new ArrayList<>();
        vis = new boolean[n + 1];
        minWeight = new int[n + 1];
        Arrays.fill(minWeight, Integer.MAX_VALUE);
        for (int i = 0; i < n + 1; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            adj.get(A).add(new Bridge(B, C));
            adj.get(B).add(new Bridge(A, C));
        }

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

        vis[fac1] = true;
        dfs(fac1);

        bw.write(Integer.toString(answer));
        br.close();
        bw.flush();
        bw.close();
    }

    static void dfs(int num) {
        if (num == fac2) {
            if (answer < minWeight[fac2]) {
                answer = minWeight[fac2];
            }

            return;
        }

        for (int i = 0; i < adj.get(num).size(); i++) {
            int nxt = adj.get(num).get(i).num;
            int curToNxtWeight = adj.get(num).get(i).weight;

            if (vis[nxt]) {
                continue;
            }

            minWeight[nxt] = Math.min(minWeight[num], curToNxtWeight);
            vis[nxt] = true;
            dfs(nxt);
            minWeight[nxt] = Integer.MAX_VALUE;
            vis[nxt] = false;
        }
    }
}

BFS + 이분탐색으로 푼 정답 코드

import java.io.*;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
    static class Bridge {
        int num, weight;

        public Bridge(int num, int weight) {
            this.num = num;
            this.weight = weight;
        }
    }

    static int n, m;
    static ArrayList<ArrayList<Bridge>> adj;
    static boolean[] vis;
    static int fac1, fac2;

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        adj = new ArrayList<>();
        vis = new boolean[n + 1];
        for (int i = 0; i < n + 1; i++) {
            adj.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            adj.get(A).add(new Bridge(B, C));
            adj.get(B).add(new Bridge(A, C));
        }

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

        int answer = binarySearch();

        bw.write(Integer.toString(answer));
        br.close();
        bw.flush();
        bw.close();
    }

    static int binarySearch() {
        int lo = 1;
        int hi = 1000000001;

        while (lo + 1 < hi) {
            int mid = (lo + hi) / 2;

            if (bfs(mid)) {
                lo = mid;
            } else {
                hi = mid;
            }
        }

        return lo;
    }

    static boolean bfs(int weight) {
        Queue<Integer> q = new LinkedList<>();
        vis = new boolean[n + 1];
        q.add(fac1);
        vis[fac1] = true;

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

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

            for (int i = 0; i < adj.get(cur).size(); i++) {
                int nxt = adj.get(cur).get(i).num;
                int curToNxtWeight = adj.get(cur).get(i).weight;

                if (vis[nxt] || curToNxtWeight < weight) {
                    continue;
                }

                q.add(nxt);
                vis[nxt] = true;
            }
        }

        return false;
    }
}