[BOJ/C++] 1939: 중량제한

🏅 Gold 3

✏️ 최종 솔루션

⭐️ 이분탐색 + BFS

1. 양방향 그래프로 다리 가중치 입력받기
2. 이분탐색
   1) while 문 돌 때마다 BFS 탐색 중 다리 방문 여부 초기화
   2) 현재 mid 값을 최대무게로 목적지 도달할 수 있으면 mid 늘려주기
3. 목적지 도달 가능한지 확인
   1) 출발지부터 시작해서 갈 수 있는 노드 큐에 넣기
   ❗️ 가중치가 mid 보다 큰 경우만 큐에 넣기 ➡️ 작은 경우는 mid 로 그 다리를 건널 수 없기 때문
   2) 목적지 도달하면 true

📌 self feedback

일단 최단거리를 간 이후에 이 경로로 간다면 최대무게가 mid 값을 넘으면 true 를 반환해서 mid 값을 늘려가야겠다고 생각했음

❗️ 애초에 TF 판단 기준을 잘못 잡음..애초에 다리 무게가 mid 값을 넘어야 다리를 건너갈 수 있기 때문에 mid 값을 넘는 다리만 큐에 넣어주어 따로 관리하고 목적지에 도달할 수 있는가를 TF 판단 기준으로 잡았어야 함
❗️ 최단거리 구할 필요없이 도착지까지 도달할 수 있는가가 관건
❗️ BFS 로 탐색할 때, 큐에서 꺼냈을 때 visit 처리하지 말고 큐에 넣을 때 visit 처리해보기
🚨 BFS 방문처리 필수적이다,,

✏️ 최종 code

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;

vector<pair<int,int>> bridge[10001];
bool visit[10001]={false};
int st,e;

bool sol(int cnt) {

    queue<int> q;
    q.push(st);
    visit[st]=true;

    bool arrived=false;
    while(!q.empty()) {
        int cur=q.front();

        q.pop();

        if(cur==e) {
            return true;
        }

        for(int i=0;i<bridge[cur].size();i++) {
            int next=bridge[cur][i].first;
            int c=bridge[cur][i].second;

            if(!visit[next] && c>=cnt) {
                visit[next]=true;
                q.push(next);
            }
        }
    }

    return false;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n,m;
    cin >> n >>m;

    int right=-1;
    for(int i=0;i<m;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        right=max(right,c);
        bridge[a].push_back({b,c});
        bridge[b].push_back({a,c});
    }

    cin >> st>>e;

    int left=1;
    int ans=-1;
    while(left<=right) {
        memset(visit, false, sizeof(visit));
        int mid=(left+right)/2;

        if(sol(mid)) {
            left=mid+1;
            ans=mid;
        }
        else right=mid-1;
    }

    cout << ans;

}