백준 1939 중량제한 Java

이분탐색 문제인 중량제한이다.

이분탐색 문제는 대체로 쉽다고 생각했는데

이분탐색에 DFS/BFS 가 섞이니까

생각보다 많이 헷갈렸다... 내가 정답률을 떨어뜨리는데 한 몫 했다.

 

문제는 마지막 줄에 주어지는 섬 두 개 사이에 물품을 옮길 때 중량의 최댓값을 출력하면 된다.

예제 입력에서 가중치를 제외하면

1 2

3 1

2 3 

인데 

마지막에 주어진 섬이 1 3 이므로

1 -> 3으로 바로 갈 수도 있고

1 ->2 ->3으로 갈 수 도 있는 것이다.

그렇기 때문에 그래프 자료구조에서 DFS / BFS를 통해 탐색해야 한다.

 

입력에 가중치가 주어지기 때문에

클래스를 하나 더 만들어서 그래프를 만들어 줘야했다.

양방향 그래프로 입력 받는다.

 

그 다음 가중치의 최솟값 -> start, 최댓값 ->end로 범위를 지정해주고

다른문제들과 마찬가지로 범위의 중간값->mid로 목표한 섬 사이 오갈 수 있는지

섬들사이의 가중치를 dfs로 비교해가며 체크한다.(bfs로도 가능하다.)

만약 중간값으로 목표한 섬 두 개를 이동할 수 있으면

start = mid+1로

mid = (start+end)/2 했을 때 중량값을 높여주고

이동할 수 없으면

end = mid-1로 중량값을 낮춰주며

 

최대로 이동할 수 있는 중량 값을 찾아낸다.

 

중량의 최댓 값은 입력받은 중량들 중의 최댓 값이다.

 

변수명들이 이상해서 헷갈리겠지만 몇 번 보면 이해할 수 있을 것이다..

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
 
public class Q1939 {
 
    static boolean check(List<Weight>[] a, int limit, int start, int end, boolean [] b) {
        if(b[start])
            return false;
        b[start] = true;
        if(start == end)
            return true;
        for(Weight v : a[start]) {
            if(v.g >= limit) {  //입력받은 중량으로 이동할 수 있는지 체크
                //return check(a, limit, v.v, end, b) 
                //이렇게 하면 check가 false 한번이라도 되면 for문이 끝나버린다. 헤맨 부분
                if(check(a, limit, v.v, end, b)){ //if문으로 해야 for문이 끝나지 않고 계속 돈다.
                    return true;
                }
            }
        }
        
        return false;
    }
 
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(); 
        int m = scan.nextInt();
        List<Weight> [] a = (List<Weight> []) new ArrayList[n+1];
 
        for(int i=1; i<=n; i++)
            a[i] = new ArrayList<>();
 
        int max = 0;
        for(int i=0; i<m; i++) {
            int v1 = scan.nextInt();
            int v2 = scan.nextInt();
            int g = scan.nextInt();
            a[v1].add(new Weight(v2, g));
            a[v2].add(new Weight(v1, g));
            max = Math.max(g, max);
        }
        int tx = scan.nextInt();
        int ty = scan.nextInt();
 
 
 
        int start = 1;
        int end = max;
        int ans = 0;
        while(start<=end) {
            boolean []b = new boolean[n+1];
            int mid = (start+end)/2;
            if(check(a, mid, tx, ty, b)) {
                start = mid+1;
                ans = Math.max(ans, mid);
            }
            else
                end = mid-1;
        }
        System.out.println(ans);
    }
 
}
class Weight{
    int v;
    int g;
 
    public Weight(int v, int g) {
        this.v = v;
        this.g = g;
    }
}