백준 알고리즘 풀이 1938번 - 중량제한

- dfs와 이분 탐색이 혼합된 문제.

반복문과 vector 배열 같은 다양한 문법을 연습할 수 있어서 좋은 문제였다고 생각한다.

- 알고리즘 -

1. <int,int>를 쌍으로 가지는 벡터 배열을 입력받아서 배열 인덱스를 from, 첫 번째 int를 to, 두 번째 int를 cost로 놓는다.

2. dfs를 사용해서 갈 수 있는지 없는지를 판단한다.

3. 갈 수 있다면, left=mid+1로, 갈수 없다면, right=mid-1으로 놓고 이진 탐색을 돌린다.

 

- 예외 조건 -

1.  그래프가 쌍방향임을 잊지말자. 처음에 vector에 넣어줄 때 양방향으로 넣어주어야 한다.

 

-소스 코드-

 

#include <iostream>
#include <vector>
#include <cstdlib>
#include <cstring>
 
using namespace std;
 
int n,m,start,ed;
vector<pair<int,int> > arr[100001];
    
bool visited[100001]={false,};
 
bool check(int num,int limit)
{
    if(visited[num]){
        return false;
    }                
    visited[num]=true;
    if(num==ed){
        return true;
    }
    for(auto &p:arr[num]){
        int next=p.first;
        int cost=p.second;
        if(cost>=limit){
            if(check(next,limit)){
                return true;
            }
        }
    }
    return false;
} 
int main()
{
    
//    다리의 갯수 : m 섬의 갯수 : n
//  마지막에 공장이 위치한 서로 다른 정수. from, to 존재 
//c가 10억까지 임을 유의 
    int left=1,right=1000000000,ans=0;    
    cin>>n>>m;
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        arr[a].push_back(make_pair(b,c));
        arr[b].push_back(make_pair(a,c));
    }
    cin>>start>>ed;
    //배열 인덱스가 시작, b가 도착지, c가 가중치 
    while(left<=right)
    {
        int mid=left+(right-left)/2;
        memset(visited,false,sizeof(visited));
        if(check(start,mid)){
            ans=mid;
            left=mid+1;
        }    
        else{
            right=mid-1;
        }            
    } 
    //dfs로.
    cout<<ans;  
}