[BOJ 1939] 중량제한 (Java)

BOJ 1939 중량제한

문제풀이

이분탐색을 풀고있어서 이분탐색 + BFS로 풀었지만 다시보니 크루스칼로 푸는게 더 쉬울거 같다. 문제는 어렵지 않았지만 그래프 문제를 풀 때 항상 주의해야하는 점인 인접행렬, 인접리스트 중 어떤 것을 사용할 것인지를 다시 한번 생각하게 된 문제다. 처음에 인접행렬을 쓰다가 메모리 초과가 났기 때문에...

1. left를 1, right를 다리의 하중 중에 최댓값으로 두고 이분탐색을 실시한다.
2. mid 값을 바탕으로 BFS 그래프 탐색을 수행해서 목적지에 도달하면 true 못하면 false
3. true면 left = mid + 1로 갱신 false면 right = mid - 1로 갱신
4. left 갱신할때 마다 mid의 최댓값을 갱신한다.

구현코드

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 class Node {
		int to, weight;
		
		Node(int to, int weight){
			this.to = to;
			this.weight = weight;
		}
	}
	
	static Queue<Integer> q;
	static boolean[] visited;
	static ArrayList<ArrayList<Node>> adj;
	static int N, M, max;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());

		max = 0;
		q = new LinkedList<>();
		visited = new boolean[N + 1];
		adj = new ArrayList<>();
		for(int i = 0 ; i <= N ; ++i) {
			adj.add(new ArrayList<>());
		}
		
		for(int i = 0 ; i < M ; ++i) {
			st = new StringTokenizer(br.readLine());
			int from = stoi(st.nextToken());
			int to = stoi(st.nextToken());
			int weight = stoi(st.nextToken());
			
			max = weight > max ? weight : max;

			adj.get(from).add(new Node(to, weight));
			adj.get(to).add(new Node(from, weight));
		}
		
		st = new StringTokenizer(br.readLine());
		int from = stoi(st.nextToken());
		int to = stoi(st.nextToken());
		
		System.out.println(binarySearch(from, to));
		
	}
	
	private static long binarySearch(int from, int to) {
		long left = 1;
		long right = max;
		long mid = 0;
		long ans = 0;
		
		while(left <= right) {
			mid = (left + right) / 2;
			
			if(go(from, to, mid)) {
				ans = mid > ans ? mid : ans;
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		
		return ans;
	}

	private static boolean go(int from, int to, long weight) {
		clear();
		
		q.offer(from);
		visited[from] = true;
		
		while(!q.isEmpty()) {
			int now = q.poll();
			
			if(now == to) {
				return true;
			}
			
			for(Node next : adj.get(now)) {
				if(!visited[next.to] && next.weight >= weight) {
					q.offer(next.to);
					visited[next.to] = true;
				}
			}
		}
		
		return false;
	}
	
	private static void clear() {
		q.clear();
		
		for(int i = 1 ; i <= N ; ++i) {
			visited[i] = false;
		}
	}

	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}