문제 : 중량제한
간단 요약
섬이 있고, 섬끼리 갈 수 있는 간선과 견딜 수 있는 하중이 있다
섬 중에 공장이 있는 두 섬이 주어졌을 때, 하중을 견디면서 두 섬 사이 옮길 수 있는 물건의 최대 중량을 구하자
데이터
구분 N M A B C 의미 섬 개수 간선 간선이 가리키는 섬1 간선이 가리키는 섬2 간선이 견딜 수 있는 하중 범위 2 ~ 10,000 1 ~ 100,000 1 ~ N 1 ~ N 1 ~ 1,000,000,000 접근법
최대 중량을 어떻게 구해야 할까?
보통 최대 하면 생각할 수 있는 방법은
- 그리디
- 이분탐색
- DP
를 생각해봐야 한다고 개인적으로 생각
DP는 이전 항(이전 단계)과의 연관성이 있어야 하는데(즉 점화식이 나와야 함)
이번 문제는 일단 Graph 탐색인 것으로 보였고, Graph 탐색에서 이전 항이라 하면 “특정 지점에 오기 전” 이라는 건데
그런 것을 통해서 얻을 수 있는 것이 없어보였으므로 DP는 제외
Greedy는 어떻게 ~하면 최대 값 같은 것이 나온다는 보장이 있어야 함
이번 문제가 Greedy라면 어떻게 해야 할까? 무슨 가정을 해야 할까?
주어진 간선 중 가장 하중을 잘 견디는 값으로 테스트 해보기?
=> 실패했다면?? 1씩 감소하면서 테스트??
=> 만약 최대 하중이 1,000,000,000이라면? 10억번을 돌아가면서 테스트하게 됨
=> 마찬가지로 하중을 가장 못견디는 값으로 테스트 해보기도 동일, 성공했다고 해도 그게 최대라는 가정이 없고 결국 1씩 올리면서 테스트 해봐야 함
이것 이외에 딱히 시도해 볼만한 가설이 없음
그렇다면 소거법으로 이분탐색이라는 말이 됨
특히 간선의 하중이 매우 크다는 점은 수상하게 여겨볼만함
O(M)의 복잡도로도 이 문제는 터질 위험이 있다는 점에서 단서가 조금 있음
그렇다면 이분 탐색을 어떻게 쓰라는 걸까?
=> 하중의 최소와 최대를 각각 범위로 잡고서 중간 값으로 시도해보며, DFS 탐색을 통해 해당 하중으로 이동이 되는지 안되는지를 테스트
=> 이를 범위를 절반씩 줄어가면서 계속 반복
끝
코드
#include <iostream> #include <vector> using namespace std; // 각 섬에 대해서 갈 수 있는 섬과 연결된 간선의 하중을 저장하는 graph vector<pair<int,int>> graph[10001]; // 각 정점에 방문했는지를 확인하기 위한 arr 변수 int arr[100001]; // 공장이 있는 섬의 좌표를 받기 위한 변수 // 시작점이 명시된 것은 아니지만 편의상 src, dst int src, dst; // 중량 확인을 위한 DFS, src지점에서 weight 무게를 견딜 수 있는지 돌면서 확인 bool DFS(int src, int weight){ // src 지점에 왔다는 체크 => src 지점으로 중복 방문을 피하기 위함 arr[src] = 1; // 만약 온 지점이 배송되어야 했던 도착 지점이라면 if(src == dst){ // 해당 weight로 배송이 가능한 것이므로 true를 반환 return true; } // src에서 갈 수 있는 간선에 대해서 탐색하면서, for(int i = 0; i < graph[src].size(); i++){ // 만약 간선으로 갈 수 있는 지점이 아직 방문한 적이 없거나, weight를 견딜 수 있을 정도의 하중으로 되어 있다면 if(arr[graph[src][i].first] == 0 && graph[src][i].second >= weight){ // 해당 지점에 대해서 DFS를 하면서 계속해서 도착점이 나올 때까지 탐색 // 만약 DFS의 결과가 true로 나왔다면 해당 weight로는 도착점까지 배송을 할 수 있는 것이므로 if(DFS(graph[src][i].first, weight)){ // 더 이상 탐색할 필요 없이 true를 반환 return true; } // 만약 false라면 계속해서 반복문을 돌아보며 다른 간선으로 해당 도착점에 갈 수 있는지 확인해보게 됨 } } // 만약 모든 간선을 돌았는데도 true 값을 반환 받지 못해서 여기까지 왔다면, 해당 weight로는 하중을 견디거나, 도착 지점까지 갈 수 있는 곳이 없으므로 false 반환 return false; } // weight 만큼 무게를 실어서 옮기는 것이 가능한지 결과를 테스트 및 반환하는 함수 bool available(int weight){ // src 지점을 weight로 방문 return DFS(src, weight); } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; for(int i = 0; i < m; i++){ int src, dst, weight; cin >> src >> dst >> weight; // 양방향이므로 각각에 대해서 간선과 하중 추가 graph[src].push_back({dst, weight}); graph[dst].push_back({src, weight}); } // 공장이 위치해 있는 섬의 좌표를 입력받음 cin >> src >> dst; // 중량을 이분 탐색으로 진행하기 위해 가장 작은 중량과 큰 중량을 left와 right로 설정 int left = 0; int right = 1000000000; // left가 right를 넘을 때까지 while(left <= right){ // DFS 탐색을 위한 사전 초기화 작업 for(int i = 0; i < 10001; i++){ arr[i] = 0; } // 이분탐색이므로 중간 값으로 mid 설정 int mid = (right + left)/2; // 해당 mid 값으로 탐색을 진행해보았을 때, 공장이 있는 섬끼리 옮길 수 있는지를 테스트 if(available(mid)){ // 옮길 수 있으면, left를 mid + 1로 설정 left = mid + 1; }else{ // 옮길 수 없으면, right를 mid -1로 설정 right = mid -1; } /** * 옮길 수 있는데도 left를 mid + 1로 옮기는 이유는 옮길 수 있는 최대 중량을 알아내기 위함 * 현재 available이 true가 나왔더라도 해당 mid 값이 옮길 수 있는 최대 중량이라는 보장이 없음 * 그렇다면 계속해서 옮겨야 하는데, left를 mid 보다 앞으로 설정하지 않으면, left가 right와 같아서 무한 while문이 반복되는 경우가 생김 * 어차피 그때의 mid 값이 최대 중량 값이었더라면, 앞으로 계속해서 false가 나오면서 right가 줄어들다가 최대 중량 + 1 값을 가리키던 left와 mid와 right가 같아지는 순간이 오고, * 이 때 수행을 해도 false가 나오면서 다시 한번 right가 mid - 1로 되면서 자연스럽게 최대 중량을 가리키게 되고, * 그 순간 left가 right보다 커지게 되면서 최적의 값을 가진 채로 while문을 탈출하게 된다 */ } // 정답 출력 cout << right; }
