[ BOJ 백준 1939번 - 중량제한 ] 해설 및 코드

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

 

목적

섬과 섬 사이에 중량제한 데이터가 주어질 때, 공장이 있는 섬을 연결하는 경로중에 중량제한이 가장 큰 경로를 구하자.

 

접근법

1. 이분탐색으로 중량을 구한 후, dfs나 bfs로 검증한다. 두 가지 방법으로 테스트해 보았다.

 

 

#include<iostream>
#include<vector>
#include<queue>
#define f(i,l,r) for(int i=l;i<r;++i)
using namespace std;
 
struct bridge { int no, lim; };
vector<vector<bridge>> v;
vector<bool> visited;
int lim, s, e;
 
bool dfs(int i) {
    if (i == e)return true;
    visited[i] = true;
    f(j, 0, v[i].size()) {
        if (visited[v[i][j].no] || v[i][j].lim < lim) continue;
        if (dfs(v[i][j].no))return true;
    }
    return false;
}
 
bool bfs() {
    queue<int> q;
    q.push(s);
    visited[s] = true;
    while (!q.empty()) {
        int i = q.front();
        q.pop();
        f(j, 0, v[i].size()) {
            if (visited[v[i][j].no] || v[i][j].lim < lim) continue;
            if (v[i][j].no == e)return true;
            visited[v[i][j].no] = true;
            q.push(v[i][j].no);
        }
    }
    return false;
}
 
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
 
    v.resize(n + 1);
    int l = 1, r = 1;
    while (m--) {
        int a, b, c; cin >> a >> b >> c;
        v[a].push_back({ b,c });
        v[b].push_back({ a,c });
        if (r < c)r = c;
    }
 
    cin >> s >> e;
    while (l <= r) {
        lim = (l + r) / 2;
        vector<bool>(n + 1, 0).swap(visited);
        if (bfs())l = lim + 1;
        else r = lim - 1;
    }
    cout << r;
}

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.