[JAVA] 백준 1939 - 중량제한

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

https://ghcode.tistory.com/286

[JAVA] 백준 1800 - 인터넷 설치

인터넷 설치 문제와 마찬가지로 이분탐색을 이용해 조건을 비교하며 범위를 줄여나가서 정답을 도출하는 문제이다.

나는 처음에 이분탐색을 돌리면서 [mid값 이하의 도로로 물건을 목적지까지 옮길 수 있는지]의 조건으로

mid < 도로 가중치 ? cost = 1 : cost = 0으로 0과 1로 이루어진 다익스트라를 돌렸는데 

이 조건이 잘못 되어서 시간을 많이 잡아먹었다.

목표하는 정보는 [mid의 무게를 지닌 물건을 목적지까지 옮길 수 있는지]이므로 도로가중치가 mid보다 크거나 같으면 cost = 0이고 작으면 cost = 1로 치환해서 문제를 풀었어야 했다.

 

시험하는 대상이 도로의 가중치인지, 아니면 값 그 자체인지 이분 탐색 조건을 확실하게 정립하고 문제를 풀어야겠다.

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] info = getArray(br.readLine());
        int nodeCount = info[0];
        int roadCount = info[1];
        List<List<P1939>> list = new ArrayList<>();
        for (int i = 0; i <= nodeCount; i++) {
            list.add(new ArrayList<>());
        }

        int max = -1;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < roadCount; i++) {
            int[] road = getArray(br.readLine());
            list.get(road[0]).add(new P1939(road[1], road[2]));
            list.get(road[1]).add(new P1939(road[0], road[2]));
            max = Math.max(road[2],max);
            min = Math.min(road[2],min);
        }
        int[] dist = new int[nodeCount + 1];
        info = getArray(br.readLine());
        int startNode = info[0];
        int endNode = info[1];
        int left = min;
        int right = max;
        int ans = -1;
        while(left<=right){
            Arrays.fill(dist,Integer.MAX_VALUE);
            int mid = (left+right)/2;
            dijkstra(dist, startNode, list, mid);
            if(dist[endNode]==0){ //mid 무게의 물건은 버팀
                ans = mid;
                left = mid+1; //더 큰 mid값도 버티는지 확인
            }else{//mid 무게를 버티지 못함
                right = mid-1; //더 작은 범위 탐색
            }
        }

        System.out.println(ans);
    }

    static void dijkstra(int[] dist, int startNode, List<List<P1939>> list, int mid){
        PriorityQueue<P1939> pq = new PriorityQueue<>();
        dist[startNode] = 0;
        boolean[] visited = new boolean[dist.length];
        pq.offer(new P1939(startNode));
        while(!pq.isEmpty()){
            P1939 poll = pq.poll();
            int value = poll.to;
            int weight = poll.weight;
            if(visited[value]) continue;
            visited[value] = true;
            List<P1939> vList = list.get(value);
            for (P1939 road : vList) {
                int to = road.to;
                int cost = road.weight;
                if (cost >= mid) cost = 0;
                else cost = 1;
                if (dist[to] > weight + cost) {
                    P1939 offer = new P1939(to);
                    offer.weight = weight + cost;
                    dist[to] = weight + cost;
                    pq.offer(offer);
                }
            }
        }
    }

    static int par(String s) {
        return Integer.parseInt(s);
    }

    static int[] getArray(String s) {
        return Arrays.stream(s.split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

class P1939 implements Comparable<P1939> {
    int to;
    int weight = 0; 

    P1939(int t) {
        this.to = t;
    }

    P1939(int t, int weight) {
        this.to = t;
        this.weight = weight;
    }

    @Override
    public int compareTo(P1939 o) {
        return this.weight - o.weight;
    }
}