[백준] 1939번 - 중량제한 (Java)

요즘은 이분탐색 문제를 풀고 있다.

이분탐색은 코드를 짜는것 자체는 어렵지 않지만, 어떤식으로 어떤 값을 탐색해나가야할지를 알아내는 것이 어렵다.

보통, 1억개 연산에 시간이 1초가 걸리기 때문에 이를 고려하여 시간초과가 날 것 같으면 이분탐색을 해야한다.

이 문제 역시, 어떤값을 이분탐색해야할지를 찾지 못해서 다른 사람의 풀이를 참고하였다.

 

 

<문제>

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

1939번: 중량제한

 

 

<풀이>

두 섬이 연결된 다리의 정보가 주어지기 때문에 그래프 탐색을 해야하는 것까지는 생각을 하였다.

일반적으로 dfs 탐색을 하여 가능한 중량의 최댓값을 구하는 것이 가능하지만, 시간초과가 발생한다. (시간 복잡도 :  N x M -> 10억 초과)

 

따라서 중량값을 이분탐색하면서 dfs로 탐색가능 여부만 파악해주면 될것이라는 풀이를 보았다. 

즉, 이분 탐색 + dfs/bfs 인 것이다.

중량값을 이분탐색으로 정하면서 탐색이 가능한 값이면 중량값을 늘려주는 식으로 탐색하여 최댓값을 찾았다.

import java.io.*;
import java.util.*;

class Node {
	int idx, limit;

	public Node(int idx, int limit) {
		this.idx = idx;
		this.limit = limit;
	}
}

class Main {
	static List<Node>[] list;
	static boolean flag = false;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int min = 0, max = 0;

		list = new List[n+1];
		for (int i = 1; i <= n; i++) {
			list[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());
			list[a].add(new Node(b,c));
			list[b].add(new Node(a,c));
			max = Math.max(max, c);
		}

		st = new StringTokenizer(br.readLine());
		int start = Integer.parseInt(st.nextToken());
		int end = Integer.parseInt(st.nextToken());

		while(min <= max) {
			int mid = (min + max) / 2;
			flag = false;
			dfs(start, end, mid, new boolean[n+1]);
			if(flag) {
				min = mid + 1;
			} else {
				max = mid - 1;
			}
		}
		br.close();
		System.out.print(max);
	}

	private static void dfs(int num, int end, int limit, boolean[] visited) {
		if(flag || num == end) {
			flag = true;
			return;
		}

		for (Node node : list[num]) {
			if(visited[node.idx] || node.limit < limit) continue;
			visited[node.idx] = true;
			dfs(node.idx, end, limit, visited);
		}
	}
}

 

 

 

아직도 이분탐색에 어려움을 겪는 것 같다.

어떤 값을 어떻게 이분탐색해야할 지 생각하는 훈련이 필요한 것 같다.

개인적으로 이분탐색에 dfs/bfs를 섞은 이문제는 좋은 문제 같다.