[백준_1939번] 중량제한

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

1939번: 중량제한

[문제]

 N(2 ≤ N ≤ 10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

 영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

 

[입력 조건]

 첫째 줄에 N, M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1 ≤ A, B ≤ N), C(1 ≤ C ≤ 1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

 

[코드]

import java.util.*;

class Point_1939 {
	int island, weight;
	
	public Point_1939(int island, int weight) {
		this.island=island;
		this.weight=weight;
	}
}
public class BaekJoon_1939 {
	static int n,m;
	static boolean[] visited;
	static ArrayList<ArrayList<Point_1939>> graph=new ArrayList<>();
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		
		for(int i=0;i<=n;i++)
			graph.add(new ArrayList<>());
		
		int max=0;
		for(int i=0;i<m;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			int w=sc.nextInt();
			
			max=Math.max(max, w); // 이분탐색의 right가 될 값 구하기(중량중 최댓 값)
			graph.get(a).add(new Point_1939(b,w));
			graph.get(b).add(new Point_1939(a,w));
		}
		
		int start=sc.nextInt(); // 시작 위치
		int end=sc.nextInt(); // 도착 위치
		
		// 이분탐색
		int left=0;
		int right=max;
		
		while(left<=right) {
			int mid=(left+right)/2;
			visited=new boolean[n+1];
			
			// mid 중량으로 start에서 end까지 이동할 수 있다면 left 증가 -> 중량이 더 무거워 짐
			if(Cross_Bridge(start,end,mid)) 
				left=mid+1;
			// mid 중량으로 start에서 end까지 이동할 수 없다면 right 감소 -> 중량이 더 가벼워 짐
			else
				right=mid-1;
		}
		
		System.out.println(right);
	}

	// start에서 end까지 이동할 수 있는지 확인하는 함수
	static boolean Cross_Bridge(int start, int end, int mid) {
		Queue<Integer> q=new LinkedList<>();
		q.add(start);
		visited[start]=true;
		
		while(!q.isEmpty()) {
			int now=q.poll();
			
			if(now==end) // end에 도달했다면 성공
				return true;
			
			for(Point_1939 next:graph.get(now)) {
				// 다음 섬이 아직 방문하지 않았으며 mid 중량이 다리를 건널수 있다면
				if(!visited[next.island]&&mid<=next.weight) {
					visited[next.island]=true; // 방문 처리
					q.offer(next.island); // 큐에 삽입
				}
			}
		}
		return false;
	}
}

 

[고찰]

 이번 문제는 이분 탐색과 BFS를 함께 사용해야 하는 문제였다. 이분 탐색을 사용해 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 설정하고, 해당 중량으로 start 지점에서 end 지점까지 이동할 수 있는지의 여부를 BFS 알고리즘으로 구성해야 정답 처리를 받을 수 있었다.

 이렇게 이분 탐색과 BFS를 접목한 문제는 처음 풀어봐서 그런지 코드를 짜면서 이런 방식으로도 문제를 해결할 수 있구나란 생각을 했다.