A. 문제설명
1939번: 중량제한
첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리
www.acmicpc.net
문제에 대한 자세한 설명은 링크 참조
1. N(2≤N≤10,000)개의 섬으로 이루어진 나라가 있음
2. 이들 사이에는 M(1≤M≤100,000)개의 다리가 설치되어 차들이 다닐 수 있음
3. 그러나 다리에는 각각 중량제한이 있어 이를 넘는 차량은 다닐 수 없음
4. 섬들과 다리의 중량제한 정보가 주어졌을 때, 출발지에서 목적지로 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하라
B. 접근법
DFS + 이분 탐색
먼저 문제의 조건을 확인하면, 주어진 메모리 제약과 함께 절대로 완전탐색으로 풀이할 수 없는 문제이다.
2 ≤ N ≤ 10,000, 1 ≤ M ≤ 100,000
4 ≤ N^2 ≤ 100,000,000
일반적으로 섬의 갯수가 작은 경우, 2차원 배열로 섬들간의 다리 정보를 구현하겠지만 여기서는 각각의 섬들이 하나 이상의 다른 섬과 이어져 있을 수도 이어져 있지 않을 수도 있으니 Pair 벡터의 동적 메모리를 사용하기로 한다.
먼저 다리의 중량 제한으로 주어진 C(1≤C≤1,000,000,000)의 상한과 하한을 frt / end로 잡고 이를 이용하여 mid를 이동해가며 DFS 탐사를 시작한다. dfs가 목적지에 도달가능하면 해답을 업데이트 후, frt를 올리고, dfs가 목적지에 도달불가하면 end를 내리며 이분탐사를 진행하여 해답을 찾을 때까지 탐색을 계속한다.
C. 풀이
1. frt를 1로, end를 1,000,000,000로 잡고, 이분탐사를 시작(1≤C≤1,000,000,000)
2. frt / end를 옮겨가며 해답을 찾을 때까지 이진탐색
3. dfs 함수는 섬에서 연결된 <다른 섬, 제한 무게> 벡터를 이용하여, 탐사되지 않은 섬 중에서 제한무게가 lmt보다 크거나 같으면 계속 탐사
4. dfs가 목적지에 도달가능하면 sol을 업데이트 후, frt를 올림
5. dfs가 목적지에 도달불가하면 end를 내림
D. 내 코드
