백준 1939 : 중량제한

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

1939번: 중량제한

 

접근방법

---

해당 문제에 이분탐색을 적용하여 해결하겠습니다.

이동하는 물품들의 중량을 정해놓고 가능한지 검사해나가면 중량의 최댓값을 구할 수 있습니다.

 

 

순서

---

1.  각 다리의 중량 제한의 최댓값을 구한다.
2.  low = 0, high = 중량의 최댓값으로 설정
3.  low와 high을 가지고 이분탐색
   1.  mid = (high + low) / 2 + 1
   2.  mid 중량으로 다리를 건널 수 있는지 체크
   3.  건널 수 있다면 low = mid으로 설정, 건널 수 없다면 high = mid - 1으로 설정

 

코드

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N, M, S, E, ans;
	static boolean[] visited;
	static ArrayList<Bridge>[] list;
	static Queue<Integer> que;
	
	static class Bridge{
		int num, wei;

		public Bridge(int num, int wei) {
			super();
			this.num = num;
			this.wei = wei;
		}
	}
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		list = new ArrayList[N + 1];
		for (int i = 1; i <= N; i++) {
			list[i] = new ArrayList<Bridge>();
		}
		
		int high = 0;
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			
			list[a].add(new Bridge(b, c));
			list[b].add(new Bridge(a, c));
			
			high = Math.max(high, c);
		}
		
		st = new StringTokenizer(br.readLine());
		S = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		
		binarySearch(0, high);
		
		System.out.print(ans);
	}

	private static void binarySearch(int low, int high) {
		if(low == high) {
			ans = high;
			return;
		}
		int mid = (low + high) / 2 + 1;
		
		if(possibleWeight(mid)) binarySearch(mid, high);
		else binarySearch(low, mid - 1);
	}

	private static boolean possibleWeight(int mid) {
		que = new LinkedList<>();
		visited = new boolean[N + 1];
		
		que.offer(S);
		visited[S] = true;
		
		while(!que.isEmpty()) {
			int num = que.poll();
			if(num == E) return true;
			
			for (int i = 0; i < list[num].size(); i++) {
				Bridge bridge = list[num].get(i);
				
				if(visited[bridge.num]) continue;
				if(bridge.wei < mid) continue;
				
				que.offer(bridge.num);
				visited[bridge.num] = true;
			}
		}
		
		return false;
	}
}

 

 

Reference

---

https://jaimemin.tistory.com/710