백준 1939번: 중량제한

백준 1939번: 중량제한

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

public class Main {
    static int N;
    static int M;
    static int start;
    static int finish;
    static ArrayList<Num> check[];
    static boolean[] visit;
    public static class Num{
        int number;
        int weight;
        public Num(int number, int weight){
            this.number = number;
            this.weight = weight;
        }
    }

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        N= sc.nextInt();
        M = sc.nextInt();
        check = new ArrayList[N+1];
        for(int i=0; i<N+1; i++){
            check[i] = new ArrayList<Num>();
        }
        int minV = 0; int maxV = Integer.MAX_VALUE;
        for(int i=0; i<M; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            minV = Math.min(minV, c);
            maxV = Math.max(maxV, c);
            check[a].add(new Num(b,c));
            check[b].add(new Num(a,c));
        }
        start = sc.nextInt();
        finish = sc.nextInt();
        int result = 0;
        while(minV<=maxV){
            int mid = (minV+maxV)/2;
            visit = new boolean[N+1];
            if(bfs(mid)){
                result=mid;
                minV=mid+1;
            }else{
                maxV=mid-1;
            }
        }
        System.out.println(result);


    }

    public static boolean bfs(int mid){
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);

        while(!queue.isEmpty()){
            int cnt = queue.poll();
            visit[cnt]=true;
            if(cnt==finish) {
                return true;
            }
            for(int i=0; i<check[cnt].size(); i++){
                Num tmp = check[cnt].get(i);
                if(tmp.weight>=mid && visit[tmp.number]==false){
                    visit[tmp.number]=true;
                    queue.add(tmp.number);
                }
            }
        }
        return false;
    }


}

bfs+이분탐색 문제다. 메모리 초과가 계속 나서 까다로웠다.....다익스트라로 푸는 방식도 있다고 한다. 다익스트라가 더 문제 출제 의도에 맞는 것 같기도? 파이썬 쓰다가 자바로 넘어오니까 자료형 쓰는 방법이나 메모리 초과 이런게 어렵다..