[백준/C++] 1939번 중량제한

백준

 

---

🤔문제 이해

한 공장에서 다른 공장으로 가는 경로 중에서 그 경로 상에 있는 중량 제한 값 중에서 최솟값을 찾고, 그 최솟값 중 가장 큰 것을 출력해주는 문제이다.

---

💡첫번째 아이디어

DFS를 통해 모든 경로를 탐색해서 그 경로의 가장 작은 중량제한 값을 저장하고 그 값들끼리 비교해서 젤 큰 값을 찾아주면 된다고 생각했다. 

 

❌첫번째 제출

섬이 1만개, 도로가 10만개로 10억번을 다 돌게 되는 첫번째 아이디어 방법으로는 시간초과가 났다.

 

💡두번째 아이디어

시간초과를 어떻게 해결해야할지 막막해서 질문을 했다. 문제에서 나와있듯 짐의 무게보다 중량제한이 작은 다리를 지나가려는 경우엔 다리가 무너진다고 했다. 이 점을 활용해서 이분탐색을 이용하여 결과를 도출해주면 1초 안에 해결이 가능했다.

 

 

🔥풀이🔥

DFS + 이분탐색

모든 경로를 탐색할 필요 없이 중량 제한값을 넘어가지 않는 경로만 찾아주면 되기 때문에 깊이 우선 탐색을 이용한다.

중량 제한 값을 이분탐색으로 /2씩 줄여가면서 경로를 찾아준다.

 

 

❌트러블 슈팅

dfs를 재귀호출할 때 다음 섬, limit을 넘겨줘야 하는데 첫번째 아이디어에서 사용했던 dfs의 습관(?)이 남아서 limit자리에 다음 섬의 중량제한 값을 넘겨주는 실수를 했다.

---

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

vector<vector<pair<int, int>>> v;
bool visited[10002];
int n, m, a, b, c;

bool dfs(int now, int limit) {
    visited[now] = true;

    if (now == b) return true;

    for (auto x: v[now]) {
        int next = x.first;
        int cost = x.second;
        if (!visited[next] && limit <= cost) {
            if (!dfs(next, limit))continue;
            else return true;
        }
    }
    return false;
}

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios::sync_with_stdio(false);

    cin >> n >> m;
    v.resize(n + 2);
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> c;
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    cin >> a >> b;

    int left = 0;
    int right = 1000000000;
    int mid, ans;
    while (left <= right) {
        memset(visited, false, sizeof(visited));
        mid = (left + right) / 2;
        if (dfs(a, mid)) {
            ans = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    cout << ans;
}