[백준] 1939 중량제한 - JAVA

문제

중량제한

풀이

처음에는 BFS만을 이용해 풀어봤지만 틀렸다.
이 문제에서 중요한 점은 두가지 인 것 같다.
1. 서로 같은 두 섬 사이에 여러 개의 다리가 있을 수 있다.
2. 공장이 있는 두 섬을 연결하는 경로는 항상 존재한다.

서로 같은 두섬 사이에 여러개의 다리가 존재하므로 BFS만을 사용하여 풀 수 없었던 것 같다. (한번 방문한 정점은 방문처리를 해주므로)

그럼 어떻게 풀어야 할까??

이 문제의 정답으로 출력할 값은 옮길 수 있는 물품들의 중량의 최댓값이다. 우리는 이 물품의 중량에 초점을 맞춰야 한다.

문제에서 나와있는 예제 입력을 예시로 들어보겠다.
1번과 2번 정점에 중량제한이 2인 다리가 있고
1번과 3번 정점에 중량제한이 3인 다리가 있고
2번과 3번 정점에 중량제한이 2인 다리가 있다.

공장의 위치는 1번과 3번에 위치한다.

1번에서 3번정점으로 갈때 다리가 무너지지 않고 갈 수 있는 중량은 다음과 같다.
1, 2, 3

여기서 최댓값은 3이므로 정답은 3이다.

이를 기초해서 이분탐색을 적용하면 다음과 같다.
먼저 입력으로 들어오는 중량중 제일 작은 중량을 low에 제일 큰 중량을 high로 둔다.
middle은 low와 high의 중간값이다.
그럼 다음과 같을 것 이다.

low,middle       high
    2             3

이제 middle에 대해서 bfs를 돌려준다. bfs에서는 한 공장에서 다른 공장으로 갈때 middle값을 가진 중량으로 다리를 안 부스고 갈 수 있는지 확인하는 용도이다.
bfs코드는 다음과 같다.

public static boolean bfs(int weight) {
    Queue<Node> q = new LinkedList<>();
    isVisit = new boolean[N+1];
    q.offer(new Node(start, 0));
    while(!q.isEmpty()) {
      Node curr = q.poll();
      if(curr.v == end) return true;
      for(Node next: graph.get(curr.v)) {
        if(weight <= next.w && !isVisit[next.v]) {
          isVisit[next.v] = true;
          q.offer(next);
        }
      }
    }
    return false;
}

bfs의 return 값이 true라면 middle 값을 가진 중량으로 다리를 건널 수 있다는 뜻이므로 중량을 더 높여준다. (low = middle + 1)
반대로 return값이 false라면 middle 값을 가진 중량으로 다리를 건널 수 없다는 뜻이므로 중량을 더 낮춘다. (high = middle - 1)

이를 코드로 나타내면 다음과 같다.

while(low <= high) {
	  int middle = (low + high) / 2;
      if(bfs(middle)) {
        low = middle + 1;
      }
      else high = middle - 1;
}

low <= high인 이유는 밑의 그림을 보고 설명하겠다.
이분탐색을 돌면 다음과 같을 것 이다.

(1)
low,middle       high
    2             3
(2)
		      low,middle,high
    2             3
(3)
		      middle,high   low 
    2             3          4
    low > high 이므로 끝

다음과 같이 low와 high의 값이 같을때도 이분탐색을 해줘야하므로 low <= high로 둔 것이다.

전체 코드

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 int answer = Integer.MIN_VALUE;
  static ArrayList<ArrayList<Node>> graph;
  static boolean[] isVisit;
  static int start,end,N;
  static class Node {
    int v,w;
    Node(int v, int w) {
      this.v = v;
      this.w = w;
    }
  }
  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());
    int M = Integer.parseInt(st.nextToken());
    graph = new ArrayList<>();

    for(int i=0; i<=N; i++) {
      graph.add(new ArrayList<>());
    }
    int low = Integer.MAX_VALUE;
    int high = Integer.MIN_VALUE;
    for(int i=0; i<M; i++) {
      st = new StringTokenizer(br.readLine());
      int v1 = Integer.parseInt(st.nextToken());
      int v2 = Integer.parseInt(st.nextToken());
      int w = Integer.parseInt(st.nextToken());
      graph.get(v1).add(new Node(v2, w));
      graph.get(v2).add(new Node(v1, w));
      low = Math.min(low, w);
      high = Math.max(high, w);
    }
    st = new StringTokenizer(br.readLine());
    start = Integer.parseInt(st.nextToken());
    end = Integer.parseInt(st.nextToken());
  
    while(low <= high) {
      int middle = (low + high) / 2;
      if(bfs(middle)) {
        low = middle + 1;
        answer = middle;
      }
      else high = middle - 1;
    }
    System.out.println(answer);
    
  }
  public static boolean bfs(int weight) {
    Queue<Node> q = new LinkedList<>();
    isVisit = new boolean[N+1];
    q.offer(new Node(start, 0));
    while(!q.isEmpty()) {
      Node curr = q.poll();
      if(curr.v == end) return true;
      for(Node next: graph.get(curr.v)) {
        if(weight <= next.w && !isVisit[next.v]) {
          isVisit[next.v] = true;
          q.offer(next);
        }
      }
    }
    return false;
  }
}