[BOJ] 백준 1939 - 중량 제한 풀이

1. 문제

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

1939번: 중량제한

 

2. 풀이 Point

• 이분 탐색 + BFS를 사용하여 해결
• 주요 자료구조
  • List<Node>[] inList : 인접리스트
  • long min : 주어진 간선 중 최솟값
  • long max : 주어진 간선 중 최대 값
  • boolean[] visited : 방문체크 배열
• 각각의 다리에 가중치가 부여되어 있고, 이 가중치를 넘지 않으면서 공장 -> 공장으로 갈 수 있는 최대 무게를 구하는 것이다.
• 이 문제에서 이분탐색의 주체는 간선의 비용이다.
• 간선의 무게를 이분 탐색으로 정한 후 start Node (이 문제에서는 첫 번째 공장)에서 end Node(두 번째 공장)까지 BFS를 실행하면서 옮길 수 있는 최대 무게를 구하는 것이 Key Point.
  
  
  

3. 풀이 Logic

• 주어진 입력으로 양방향 인접리스트를 구성한다.
• 입력을 받을 때 간선의 최솟값과 최댓값을 구한다.
  • 이는 후에 이분 탐색의 left, right 값에 활용한다.
• 이분 탐색 함수인 weightRestrictionBinarySearch()를 실행한다.
  • 간선의 최댓값과 최솟값을 left, right 로 설정하여 이분탐색의 양 끝 값을 설정한다.
  • left <= right 일 때까지 (left + right) / 2를 하여 mid 값을 정한다.
  • 이 mid 값을  weightRestrictionBFS()에 보내어 BFS를 실행한다.
    1. BFS 함수를 실행할 때는 Queue에서 꺼낸 객체가 end Node, 즉 두 번째 공장이라면 True를 리턴하고, 두 번째 공장까지 탐색할 수 없다면 False를 리턴한다.
    2. 이 때, 주의해야할 점은, 다음 노드를 탐색할 때 "mid가 다음 노드 간선의 가중치보다 작거나 같을 때 탐색할 수 있다"
    3. 왜냐하면 다리를 건너려면 그 간선의 가중치보다 작거나 같아야 하기 때문이다.
  • 만약 weightRestrictionBFS()에서 리턴받은 값이 True라면, 설정한 mid 값으로 목적지에 도달했다는 것이므로 결과를 갱신하고 left 값을 mid + 1 한다.
  • 만약 리턴받은 값이 False라면, 목적지에 도달하지 못했다는 것이므로 이는 값을 줄여야 한다. 따라서 right에 mid - 1 한 값을 대입한다.
   

4. 소스 코드

import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int N; // 섬의 개수
	static int M; // 다리의 개수
	
	static class Node {
		int v;
		long cost;
		
		public Node(int v, long cost) {
			this.v = v;
			this.cost = cost;
		}
	}
	
	static List<Node>[] inList; // 인접 리스트
	static long result = Integer.MIN_VALUE;
	
	static int start, end;
	static long min = Integer.MAX_VALUE; // 주어진 간선 중 최솟값
	static long max = Integer.MIN_VALUE; // 주어진 간선 중 최대 값
	
	static boolean[] visited;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        // 입력을 받아 변수 초기화 및 인접리스트 초기화
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        inList = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
        	inList[i] = new ArrayList<>();
        }
        
        for (int i = 0; i < M; i++) {
        	st = new StringTokenizer(br.readLine());
        	int from = Integer.parseInt(st.nextToken());
        	int to = Integer.parseInt(st.nextToken());
        	int cost = Integer.parseInt(st.nextToken());
        	
        	inList[from].add(new Node(to, cost));
        	inList[to].add(new Node(from, cost));
        	
        	// 간선의 최대값 구하기
        	min = Long.min(min, cost);
        	max = Long.max(max, cost);
        }
        
        // 출발 노드 번호 및 도착 노드 번호
        st = new StringTokenizer(br.readLine());
        start = Integer.parseInt(st.nextToken());
        end = Integer.parseInt(st.nextToken());
        
        // 이분탐색 함수 시작
        weightRestrictionBinarySearch();
        
        //결과 출력
        bw.write(Long.toString(result));
        bw.flush();
        bw.close();
        br.close();
    }

    // 이분 탐색 함수 : 이분탐색의 주체는 간선의 비용
	private static void weightRestrictionBinarySearch() {
		long left = min;
		long right = max;
		
		// weightRestrictionBFS의 리턴 값은 true or false
		// 만약 true가 리턴 됬다는 것은 도착지점에 도착했다는 것이므로 result를 갱신
		while (left <= right) {
			long mid = (left + right) / 2;
			
			if (weightRestrictionBFS(mid)) {
				result = Long.max(result, mid);
				
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
	}
	
	// bfs 함수
	private static boolean weightRestrictionBFS(long mid) {
		// 방문 배열
		visited = new boolean[N + 1];
		
		// BFS를 위한 큐
		Queue<Node> q = new ArrayDeque<>();
		q.add(new Node(start, mid));
		visited[start] = true;
		
		while (!q.isEmpty()) {
			Node poll = q.poll();
			
			// 두번째 공장에 도착했다면
			if (poll.v == end) {
				return true;
			}
			
			for (int i = 0; i < inList[poll.v].size(); i++) {
				// 연결된 노드가 null이 아니고, 방문 처리하지 않았고, 
				// 지금 탐색하는 cost가 다음 노드 간선의 cost보다 작거나 같을 때 탐색할 수 있음
				if (inList[poll.v].get(i) != null && !visited[inList[poll.v].get(i).v]
						&& mid <= inList[poll.v].get(i).cost) {
					visited[inList[poll.v].get(i).v] = true;
					q.add(new Node(inList[poll.v].get(i).v, mid));
				}
			}
		}
		return false;
	}
}

5. 점수

65 / 100