[백준] 1939 중량제한 - 파라매트릭 서치(Paramatric Search) + BFS(너비우선탐색) JAVA

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

1939번: 중량제한

코드설명

파라매트릭 서치와 BFS를 함께 사용합니다.

 

중량제한을 초과하지 않기 위해 적정한 무게를 찾기 위한 작업을 진행합니다.

물론, BFS를 무게별로 모두 진행시켜서 1,000,000,000 만큼의 BFS를 진행시켜서 구할수도있겠지만, 그렇게할경우 무게가 10억번에다가 각 Node의 연결관계를 고려하였을떄 O( C * N ) 최악의 경우 이러한 시간복잡도가 나옵니다.

 

그렇기에 파라매트릭 서치를 활용하여 탐색시간을 log N 으로 줄여 O(log N * N) 으로 시간을 감소시킬 수 있습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	
	public static int N, M, L;
	public static int[] arr;
	public static int targetStart = 0, targetEnd = 0;
	public static int answer = 0;
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
	
    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());
    	
    	for(int i=0;i<=N;i++) {
    		graph.add(new ArrayList<Node>());
    	}
    	
    	int maxWeight = 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());
    		
    		graph.get(a).add(new Node(b, c));
    		graph.get(b).add(new Node(a, c));
    		maxWeight = Math.max(maxWeight, c);
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	targetStart = Integer.parseInt(st.nextToken());
    	targetEnd = Integer.parseInt(st.nextToken());
    	
    	paramatricSearch(0, maxWeight);
    	
    }
    
    public static void paramatricSearch(int startWeight, int endWeight) {
    	int left = startWeight;
    	int right = endWeight;
    	
    	while(left <= right) {
    		int middle = (left + right) / 2;
//    		System.out.println("middle:"+middle);
    		//middle값의 무게로 다리를 건널 수 있는지 확인하는 그래프 탐색 함수를 작성합니다.
    		if( BFS(middle) == true ) { //다리를 옮길 수 있따면 무게를 더 올려서 이분탐색을 시행한다.
    			left = middle + 1;
    		} else {
    			right = middle - 1;
    		}
    	}
    	System.out.println(right);
    	
    	
    } 
    
    public static boolean BFS(int weight) {
    	Queue<Integer> q = new LinkedList<>();
    	boolean[] visited = new boolean[N + 1];
    	q.offer(targetStart);
    	visited[targetStart] = true;
    	while(!q.isEmpty()) {
    		int temp = q.poll();
//    		System.out.println(temp);
    		if(temp == targetEnd) {
    			return true;
    		}
    		
    		for(int i=0;i<graph.get(temp).size();i++) {
    			Node next = graph.get(temp).get(i);
    			if(visited[next.nodeB] == true) continue; //이미 방문했다면 못갑니다.
    			if(next.weight < weight) continue; //이미 다음의 무게를 초과한다면, 못갑니다. 
    			
    			visited[next.nodeB] = true;
    			q.offer(next.nodeB);
    		}
    		
    	}
    	
    	return false;
    	
    }
    
}


class Node{
	int nodeB;
	int weight;
	public Node(int nodeB, int weight) {
		this.nodeB = nodeB;
		this.weight = weight;
	}
}

 

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 {
	
	public static int N, M;
	public static int[][] map;
	public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
	public static int answer = -1;
	public static int maxWeight = 0;
	public static int left = 0, right = 0, startNodeIdx = 0, endNodeIdx = 0;
	public static boolean[] visited;
	public static StringBuilder sb = new StringBuilder();
	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());
    	
    	for(int i=0;i<=N;i++) {
    		graph.add(new ArrayList<Node>());
    	}
    	
    	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());
    		graph.get(A).add(new Node(B, C));
    		graph.get(B).add(new Node(A, C));
    		
    		maxWeight = Math.max(maxWeight, C);
    	}
    	
    	st = new StringTokenizer(br.readLine());
    	startNodeIdx = Integer.parseInt(st.nextToken());
    	endNodeIdx = Integer.parseInt(st.nextToken());
    	
    	left = 0; right = maxWeight;
    	paramatricSearch(left, right);
    	
    	System.out.println(answer);
	}
	
	public static void paramatricSearch(int leftWeight, int rightWeight) {
		
		while(leftWeight <= rightWeight) {
			int midWeight = (leftWeight + rightWeight) / 2;
			visited = new boolean[N+1];
			if(BFS(midWeight) == true) { //더 크게옮긴다.
				leftWeight = midWeight + 1;
			}else {
				rightWeight = midWeight - 1;
			}
		}
		answer = rightWeight;
	}
	
	public static boolean BFS(int midWeight) {
		Queue<Integer> q = new LinkedList<>();
		q.offer(startNodeIdx); //주어진 시작점에서 시작한다.
		visited[startNodeIdx] = true; //방문한 곳을 방문처리한다.
		
		while(!q.isEmpty()) {
			int tempIdx = q.poll();
			if(tempIdx == endNodeIdx) { //만약 성공적으로 이동했다면 해당 무게로 옮길 수 있다는 것 입니다.
				return true;
			}
			
			for(int i=0;i<graph.get(tempIdx).size();i++) {
				if(visited[graph.get(tempIdx).get(i).nodeB] == false && midWeight <= graph.get(tempIdx).get(i).weight) { //만약 지나갈 수 있는 무게라면, 지나간다.
					visited[graph.get(tempIdx).get(i).nodeB] = true;
					q.offer(graph.get(tempIdx).get(i).nodeB);
				}
			}
			
		}
		return false;  
	}
}

class Node{
	int nodeB;
	int weight;
	public Node(int nodeB, int weight) {
		this.nodeB = nodeB;
		this.weight = weight;
	}
}