백준 1939 JAVA : 중량제한

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

1939번: 중량제한

 

---

풀이방법

중량 제한인 C 의 범위가 커서 (1<= C <= 1,000,000,000) 이분탐색을 적용했다.

 

1. 다리 정보들을 다 받아서 ArrayList에 연결시켜 놓는다.

2. 끝점에 연결되어 있는 노드를 전부 탐색 후 최대 중량제한 값(right)을 구한다.

3. 0부터 구한 최대 중량제한 값(right) 사이를 이분탐색을 진행한다. (mid 값으로 bfs 돌렸을 때, 가능하다면 left값 변경, 아니라면 right값 변경)

 

주의할점

처음에 이분탐색 범위를 끝점에 연결되어있는 노드의 최소 중량제한 ~ 최대 중량제한 까지로 설정했었는데 최소 중량제한보다 중간에 더 작아질 수 있어서 최대 중량제한까지만 설정해 두어야 한다.

 

 

소스코드

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

public class Main {
    static int N,M;
    static ArrayList<Node> [] list;
    static class Node {
        int next;
        long w;

        public Node(int next, long w) {
            this.next = next;
            this.w = w;
        }
    }
    static int start,end;
    static long left = 0,right = Long.MIN_VALUE;
    static boolean visited[];
    static long result;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        list = new ArrayList[N+1];

        for (int i = 0; i <= N; i++) { //리스트 초기화
            list[i] = 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());
            long c = Long.parseLong(st.nextToken());

            list[a].add(new Node(b,c));
            list[b].add(new Node(a,c));
        }

        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());


        for (int i = 0; i < list[end].size(); i++) {
            right = Math.max(right, list[end].get(i).w);
        }
        
        //이분탐색
        while(left<=right) {
            long mid = (left+right) / 2;

            if(bfs(mid)) {
                left = mid +1;
                result = Math.max(result, mid);
            }else {
                right = mid-1;
            }
        }

        System.out.println(result);

    }

    private static boolean bfs(long mid) {
        visited = new boolean[N+1];
        visited[start] = true;
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);

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

            for (int i = 0; i < list[cur].size(); i++) {

                if(list[cur].get(i).w>=mid && list[cur].get(i).next == end) {
                    return true;
                }

                if(!visited[list[cur].get(i).next] && list[cur].get(i).w >= mid) {
                    visited[list[cur].get(i).next] = true;
                    q.offer(list[cur].get(i).next);
                }
            }

        }

        return false;
    }
}

 

 

결과