[알고리즘] 중량제한 (백준 1939번)

1939번: 중량제한

 전형적인 'BFS + BinarySearch' 유형의 문제이다. BinarySearch로 최대값 혹은 최소값을 찾되 BFS로 현재 값이 타당한지를 판단하는 문제 유형이다.

 

Solution

 이 문제는 트럭에 실릴 수 있는 최대 중량을 구하라는 문제이다.

 만약 트럭의 특정 중량을 기준으로 도착지까지 갈 수 없다면, 그보다 더 높은 중량으로는 당연히 도착지까지 갈 수가 없기에 search하는 값들이 정렬이 되어 있기에 이분 탐색 적용이 가능하다.

 이분 탐색의 left는 트럭의 최소 중량이 될 것이고 right는 최대 중량이 될 것이며 최대 중량은 입력된 다리들의 한계 중량 중 최대값을 설정하면 된다.

 그리고 BFS로 출발지 → 도착지로 트럭이 이동하되 다리를 이동할 땐 현재 트럭의 중량 weight가 다리의 한계중량 limit 이하인 경우에만 이동할 수 있다. 도착지까지 이동가능하면 true, 아니면 false를 반환한다.

 

1. 각 섬마다 연결되어있는 다리의 목록을 저장하는 이중 ArrayList bridges 객체를 만든다.
2. 다리와 연결된 섬과 한계중량을 포함하는 Bridge 클래스를 만든다.
3. binarySearch 시작
   1. left = 1
   2. right = max_weight (다리 중 최대 한계중량)
   3. mid = (left + right) / 2
   4. bfs(mid) 의 결과가 true 라면 탐색 범위를 오른쪽 절반으로 줄인다 (최대 중량을 올린다.) → left = mid + 1
   5. bfs(mid) 의 결과가 false 라면 탐색 범위를 왼쪽 절반으로 줄인다 (최대 중량을 낮춘다.) → right = mid - 1
   6. left = right가 되어 가능한 최대 중량을 구할 때까지 반복
4. binarySearch의 반환값 최대 중량을 출력

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

	static int max_weight = 0;

	static ArrayList<ArrayList<Bridge>> bridges = new ArrayList<>();
	static int start, finish;

	static void solution() throws  Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer strtok = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(strtok.nextToken());
		int M = Integer.parseInt(strtok.nextToken());


		for(int i = 0;i <= N;i++)
			bridges.add(new ArrayList<>());

		for(int i = 0;i < M;i++)
		{
			strtok = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(strtok.nextToken());
			int b = Integer.parseInt(strtok.nextToken());
			int c = Integer.parseInt(strtok.nextToken());

			bridges.get(a).add(new Bridge(b, c));
			bridges.get(b).add(new Bridge(a, c));

			max_weight = Math.max(max_weight, c);
		}

		strtok = new StringTokenizer(br.readLine());

		start = Integer.parseInt(strtok.nextToken());
		finish = Integer.parseInt(strtok.nextToken());

		bw.write(binarySearch(N)+"");
		bw.close();
	}

	//1~max_weight 까지 중량탐색
	static int binarySearch(int N)
	{
		int left = 1;
		int right = max_weight;

		int max = 0;

		while(left <= right)
		{
			int mid = (left + right) / 2;

			if(bfs(N, mid))
			{
				max = Math.max(max, mid);
				left = mid + 1;
			}
			else
				right = mid - 1;

		}

		return max;
	}

	//weight : 현재 트럭의 무게
	static boolean bfs(int N, int weight)
	{
		Queue<Integer> queue = new LinkedList<>();

		boolean visited[] = new boolean[N+1];

		queue.offer(start);
		visited[start] = true;

		while(!queue.isEmpty())
		{
			int now = queue.poll();

			if(now == finish)
				return true;

			for(int i = 0;i < bridges.get(now).size();i++)
			{
				Bridge bridge = bridges.get(now).get(i);

				int next = bridge.to;
				int limit = bridge.weight;

				//limit 한계중량 초과안하면 이동가능
				if(!visited[next] && weight <= limit)
				{
					visited[next] = true;
					queue.offer(next);
				}
			}
		}

		return false;
	}


	static class Bridge{
		int to;
		int weight;

		public Bridge(){}

		public Bridge(int to, int weight)
		{
			this.to = to;
			this.weight = weight;
		}

	}


	public static void main(String[] args) {

		try
		{
			solution();
		}
		catch (Exception e)
		{
			e.printStackTrace();
		}
	}


}