[BaekJoon] 1939. # 중량제한

[BaekJoon] 1939. # 중량제한

Question

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

출력

첫째 줄에 답을 출력한다.

Solution

풀이

1) bfs (시간초과)

• 다리를 매번 방문해서 확인하니 1만개의 섬, 10만개의 다리정보가 있는 경우 O(N * M)으로 1억 넘게 연산이 발생함. => bft + binary search로 문제 해결
• 추가적으로 Bridge구조를 List에서 ArrayList[]로 변경하여, search 시 특정 섬을 기준으로 어떤 다리들이 있는 지 확인할 수 있도록 함.

import java.util.Scanner; 
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.LinkedList;

public class Main { 
    public static void main(String[] args) throws Exception { 
        Scanner scn = new Scanner(System.in);
        int N = scn.nextInt(); // 섬의 개수 
        int M = scn.nextInt(); // 다리 정보  

        // 다리 데이터 저장 
        List<Bridge> bridgeList = new ArrayList<Bridge>();
        for (int i = 0; i < M; i++)
            bridgeList.add(new Bridge(scn.nextInt(), scn.nextInt(), scn.nextInt()));
  
        // 공장 데이터 저장       
        int factoryStart = scn.nextInt();
        int factoryEnd = scn.nextInt();
        
        // 공장 다리 검증 
        int[] visited = new int[N + 1];
        Queue<Bridge> checkBridgeList = new LinkedList<Bridge>();
        checkBridgeList.add(new Bridge(factoryStart, 0, 0));
        
        int maxWeight = 0; 
        while (!checkBridgeList.isEmpty())
        {
            Bridge curBridge = checkBridgeList.remove(); 
            visited[curBridge.start] = 1; 
            
            
            for (Bridge bridge : bridgeList)
            {
                // 공장 도달했다면 최대값 검증 
                if (bridge.start == curBridge.start && bridge.end == factoryEnd || bridge.end == curBridge.start && bridge.start == factoryEnd )
                {
                    maxWeight = Math.max(maxWeight, bridge.weight);
                }
                else {
                    if (bridge.start == curBridge.start && visited[bridge.end] != 1) 
                        checkBridgeList.add(new Bridge(bridge.end, bridge.start, Math.min(bridge.weight, curBridge.weight)));
                    else if (bridge.end == curBridge.start && visited[bridge.start] != 1)
                        checkBridgeList.add(new Bridge(bridge.start, bridge.end, Math.min(bridge.weight, curBridge.weight)));
                }
            }
            
        }
        
        
        System.out.println(maxWeight);
        
    } 
}

class Bridge { 
    int start;
    int end;
    int weight; 
    
    public Bridge(int start, int end, int weight) {
        this.start = start;
        this.end = end; 
        this.weight = weight; 
    }
}

2) bfs + binarysearch

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.LinkedList;
import java.io.BufferedReader;
import java.util.StringTokenizer;
import java.io.InputStreamReader;

public class Main { 
    public static void main(String[] args) throws Exception { 
        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());
        
        // 다리 데이터 저장
        ArrayList<Bridge>[] bridgeList = new ArrayList[N + 1];
        
        for(int i=0; i<N+1; i++)
            bridgeList[i] = new ArrayList<>();
        
        int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE;
        for (int i = 0; i < M; i++)
        {
            st = new StringTokenizer(br.readLine());
            int tempStart = Integer.parseInt(st.nextToken());
            int tempEnd = Integer.parseInt(st.nextToken());
            int tempWeight = Integer.parseInt(st.nextToken());
            
            min = Math.min(tempWeight, min);
            max = Math.max(tempWeight, max);
            
            bridgeList[tempStart].add(new Bridge(tempEnd, tempWeight));
            bridgeList[tempEnd].add(new Bridge(tempStart, tempWeight));
        }
        
        int mid = 0;      
        // 이진 탐색 
        while (min <= max)
        {
            mid = (min + max) / 2;
            
            Queue<Integer> checkBridgeList = new LinkedList<Integer>();
            boolean[] visited = new boolean[N + 1];
            checkBridgeList.add(factoryStart);
            
            boolean isPossible = false;
            while (!checkBridgeList.isEmpty())
            {
                int curBridge = checkBridgeList.poll(); 
                visited[curBridge] = true; 
                
                // 공장 도달했다면 최대값 검증 
                if (curBridge == factoryEnd)
                {
                    isPossible = true; 
                    break;
                }
    
                for (Bridge bridge : bridgeList[curBridge])
                {
                    // 아직 미방문한 경우 
                    if (visited[bridge.end] != true && bridge.weight >= mid) {
                        visited[bridge.end] = true;
                        checkBridgeList.offer(bridge.end);
                    }
                }
            }
            
            // 추정값이 현재무게보다 크다면 
            if (isPossible)
                min = mid + 1;
            else 
                max = mid - 1;
        }
        
        
        System.out.println(max);
    } 
}
class Bridge { 
    int end;
    int weight; 
    public Bridge(int end, int weight) {
        this.end = end; 
        this.weight = weight; 
    }
}

Learning…

• 다리 정보 자료구조 개선
  • Bridge(start, end, weight) -> List(Bridge(end,weight))

Reference

• BaekJoon