<Baekjoon> #1939 중량제한_Binary Search, DFS java

#1939 중량제한

Solution

• 답으로 구해야하는 것이 무엇인지 생각해볼 필요가 있는 문제였다
  → "한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값"을 구하는 문제이다
• 일반 그래프 문제에서 요구하는 최소 이동거리, cost의 최소 등과는 다르다
  → A에서 출발해서 B로 가는 지점 중 다리의 중량이 최대인 것만 구하면 된다
  → 다리 중량(W)을 선택해서 DFS 탐색을 해보며 A지점에서 B지점으로 가는 길 중에서 W보다 큰 중량을 가진 다리가 있는지 살펴본다
• 각 다리의 중량 제한은 최소 1에서 최대 1,000,000,000(이하 1억개)이다
  → 이진 탐색을 통해 범위를 좁혀가보며 중량을 선택해서 DFS 탐색을 시도한다

Binary Search

• 우선 이진 탐색은 다음과 같은 구조를 따른다

  int low=0, high=1_000_000_000;
  while (low<=high) {
      int mid=(low+high)/2;

      if (상황에 맞는 조건 문) {
          ans=mid;
          low=mid+1;
      }
      else high=mid-1;
  }

• 이 문제에서는 int low=0, high=1_000_000_000; 사이에서 한 값을 선택해서 이 값이 최대 중량이라고 가정하고 시작점에서 도착점까지 이 값보다 더 큰 중량을 가진 다리가 있는지, 없는지 판단한다
• 이때 더 큰 중량을 가진 다리가 있는 상태로 도착점에 도착했다면 더 큰 범위에서 다시 탐색하고, 그렇지 않다면 더 작은 범위에서 탐색을 한다

DFS

• 현재 도착한 다리가 v, 최대 중량이라고 가정한 무게가 w일 때 탐색을 진행한다
• 다리가 최종 목적지에 도착하면 true를 return 하게 되는데 이 의미는 최대 중량이라고 가정한 무게 w보다 더 큰 무게를 가진 다리가 있는 상태로 최종 목적지에 도착했다는 뜻이다
  → 이진 탐색으로 돌아가서 더 큰 범위에서 다시 찾아본다
• false를 return 한다는 것은 현재 최대 중량이라고 가정한 무게 w보다 모두 작은 중량을 가지고 있다는 의미이므로 이진탐색으로 돌아가서 더 작은 범위에서 다시 찾아보아야 한다

  private static boolean dfs (int v, int w) {
      visited[v]=true;
      if (v==end) return true;

      for (Edge e : edgeList[v]) {
          if (!visited[e.v] && e.w>=w) {
              if (dfs (e.v, w)) return true;
          }
      }
      return false;
  }

Source Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

	static int N, M,start,end,ans;
	static List<Edge> edgeList[];
	static boolean[] visited;
	
	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());
		
		visited=new boolean[N+1];
		
		edgeList=new ArrayList[N+1];
		for (int i=0; i<N+1; i++)
			edgeList[i]=new ArrayList<>();
		
		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());
			
			edgeList[A].add(new Edge (B,C));
			edgeList[B].add(new Edge (A,C));
		}
		st=new StringTokenizer (br.readLine());
		start=Integer.parseInt(st.nextToken());
		end=Integer.parseInt(st.nextToken());
	
		int left=0, right=1_000_000_000;
		while (left<=right) {
			int mid=(left+right)/2;

			if (dfs (start, mid)) {
				ans=mid;
				left=mid+1;
			}
			else right=mid-1;
			
			Arrays.fill(visited, false);
		}
		
		System.out.println(ans);
	}
	

	private static boolean dfs (int v, int w) {
		visited[v]=true;
		if (v==end) return true;

		for (Edge e : edgeList[v]) {
			if (!visited[e.v] && e.w>=w) {
				if (dfs (e.v, w)) return true;
			}
		}
		return false;
	}

	
	static class Edge {
		int v;
		int w;
		
		Edge (int v, int w) {
			this.v=v;
			this.w=w;
		}
	}
}