[PS] BOJ1939 중량제한 ( BinarySearch + BFS ) with JAVA

1939번: 중량제한

 

◎ 문제풀이 

 

공장1에서 공장2로 한번에 이동가능한 최대중량을 구하는 문제이다.

 

BinarySearch와 BFS를 모두 떠올려야 하는 고난도 문제였다. 처음 이 문제를 접했을 때, DFS가 떠올랐다. 공장1에서 공장2까지 가는 모든 경로를 완전탐색해야 한다고 생각했기 때문이다. 그러나 DFS로 풀면 시간초과가 난다. 

 

visited[bridge.nextNode] = true; // 역행방지 
dfs(bridge.nextNode,dest, min(limit,bridge.limit));
visited[bridge.nextNode] = false; // 완전탐색을 위해 원복

 

위 코드처럼, 역행방지를 위한 방문여부만 체크할 뿐, 탐색이 끝나면 다시 방문여부를 원복하여 완전탐색을 하였다. 이렇게 하면 이미 방문한 노드를 다시 한번 방문하게 되므로, 시간복잡도는 O(VE) ( 노드의 개수(V), 간선의 개수(E) )가 된다.  V가 최대 1,000이고 E가 최대 100,000이다 . 백트래킹 조건도 없으므로 시간제한 1초로는 어림없다. 

 

그러므로 발상을 바꾸어야 한다. 

 

탐색을 하며 최대중량을 구하는 것이 아니라, 가능한 중량의 범위를 좁혀가며 탐색을 해야 한다. 중량의 범위는 1 부터 1억 사이다.  이 범위 안에서 최대중량을 구해야 한다. 이분탐색을 하면 O(logN)으로 최대중량을 구할 수 있다. 그럼 어떻게 최대중량은 구할까? 이분탐색마다 BFS 탐색을 하는 것이다. 

 

이분탐색으로 중간중량을 구한다. 중간중량으로 BFS 탐색을 하여 공장1에서 공장2로 이동이 가능여부를 확인한다. 이동이 가능한 중간중량을 찾아도  최대중량이라는 보장이 없다. 그러므로 중간무게보다 더 큰 우측범위를 탐색한다. 만약 이동이 가능하지 않는다면 좌측 범위를 탐색한다. 이렇듯 중간중량으로 공장1에서 공장2로 이동 가능 여부만 빠르게 파악해야 하므로, 최단경로를 구할 때 사용하는 BFS를 사용해야 한다. BFS의 시간복잡도는 O(V+E)이다. 

 

고로, 전체 시간복잡도는 O( (V+E)*logN ) 이다. V+E 가 최대 110,000이니 시간제한에 걸리지 않는다. 

 

◎ 코드

package org.example.binarySearch;


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

//BOJ1939 중량제한 ( BinarySearch + BFS  )
public class Bs7 {


    public static List<Bridge>[] bridges;
    public static boolean[] visited;
    public static int ans,n,m;
    public static int factoryNode1;
    public static int factoryNode2;

    public static class Bridge {
        int nextNode;
        int weight;

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

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

        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        bridges = new List[n+1];

        for(int i=0;i<n+1;i++){
            bridges[i] = new ArrayList<>();
        }

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());

            int node1 = Integer.parseInt(st.nextToken());
            int node2 = Integer.parseInt(st.nextToken());
            int limit = Integer.parseInt(st.nextToken());

            bridges[node1].add(new Bridge(node2,limit));
            bridges[node2].add(new Bridge(node1,limit));
        }

        st = new StringTokenizer(br.readLine());

        factoryNode1 = Integer.parseInt(st.nextToken());
        factoryNode2 = Integer.parseInt(st.nextToken());

        int ans = binarySearch(1,1000000000); // 이분탐색 시작
        System.out.println(ans);

    }

    public static int binarySearch(int left, int right){
        if(left > right) return right;

        int mid = ( left + right ) / 2 ;

        if(bfs(mid)) return binarySearch(mid+1, right); // 중간중량이 이동가능하다면 우측범위 탐색
        else return binarySearch(left, mid-1); // 중간중량이 이동이 불가능하다면 좌측범위 탐색
    }

    //BFS 로직
    public static boolean bfs(int weight) {
        Queue<Bridge> queue = new LinkedList<>();
        visited = new boolean[n + 1];
        addInQueue(weight,factoryNode1,queue); // 시작지점 큐에 넣기 

        while (!queue.isEmpty()) {
            Bridge curr = queue.remove();
            if (curr.nextNode == factoryNode2) return true;
            addInQueue(weight,curr.nextNode,queue);
        }

        return false;
    }

    private static void addInQueue(int weight, int node, Queue<Bridge> queue) {
        for (Bridge bridge : bridges[node]) {
            if( weight <= bridge.weight && !visited[bridge.nextNode]) {
                queue.add(bridge);
                visited[bridge.nextNode] = true;
            }
        }
    }

}