문제 풀이(53)

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

import java.util.*;
import java.io.*;



class Edge{
    int vertex,  value;

    Edge(int vertex , int value)
    {
        this.vertex = vertex;
        this.value = value;
    }


}


public class Main {

    static int N,M, start, end;
    static ArrayList<Edge>[] adj;
    static boolean[] visited;
   

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

        visited = new boolean[N + 1];

        adj = new ArrayList[N + 1];

        for (int i = 0; i <= N; i++) {
            adj[i] = new ArrayList<>();
        }

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

            int s = Integer.parseInt(st.nextToken());

            int e = Integer.parseInt(st.nextToken());

            int v = Integer.parseInt(st.nextToken());

            adj[s].add(new Edge(e, v));
            adj[e].add(new Edge(s, v));
        }

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

        start = Integer.parseInt(st.nextToken());

        end = Integer.parseInt(st.nextToken());


        int left = 0, right = 1000000000, res = 0;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (function(mid)) {
                res = mid;
                left = mid + 1;
            }else{
                right = mid - 1;
            }
        }

        System.out.println(res);
        
       
    }

    public static boolean function(int weight)
    {
        visited = new boolean[N + 1];

        Queue<Integer>Q = new LinkedList<>();

        visited[start] = true;

        Q.offer(start);

        while (!Q.isEmpty()) {
            int current = Q.poll();

            if (current == end) {
                return true;
            }

            for(Edge e : adj[current])
            {

                if (!visited[e.vertex] && e.value >= weight) {
                    Q.offer(e.vertex);
                    visited[e.vertex] = true;
                }
            }
        }

        return false;
    }
}

이분탐색: 가능한 중량제한의 최소값(left)과 최대값(right)을 설정하고, 이진 검색을 통해 최대 중량을 결정합니다. 이 과정에서 function 메소드를 사용하여 중간값(mid)을 중량제한으로 했을 때 두 섬 사이를 이동할 수 있는지 확인한다.

경로 검증: function 메소드는 주어진 중량제한으로 시작 섬부터 끝 섬까지 도달 가능한지 BFS(너비 우선 검색)를 사용하여 확인한다. 중량제한 이상인 다리만을 거쳐 이동이 가능한지 확인하며, 끝 섬에 도달할 수 있다면 true를, 그렇지 않다면 false를 반환한다.

결과 출력: 이진 검색을 통해 확인된 최대 중량제한 값을 출력한다.