[백준 1939] 중량제한

[백준 1939] 중량제한

문제 링크

#include "header.h"
#define MAX 1000000000
using namespace std;
int N, M;
int x, y;
int visit[10001];
vector<pair<int, int>> graph[100001];
void input() {
    cin >> N >> M;

    int a, b, c;

    for (int i = 0; i < M; i++) {
        cin >> a >> b >> c;
        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }

    //공장이 위치한 곳
    cin >> x >> y;
}
bool bfs(int mid) {

    memset(visit, 0, sizeof(visit));
    queue<int> q;
    q.push(x);
    visit[x] = 1;

    while (!q.empty()) {
        int top = q.front();
        q.pop();

        //도착 했을 경우
        if (top == y) {
            return true;
        }

        for (int i = 0; i < graph[top].size(); i++) {
            int next = graph[top][i].first;
            int cost = graph[top][i].second;

            //top 연결된 것들 중
            if (!visit[next] && mid <= cost) {
                visit[next] = 1;
                q.push(next);
            }
        }
    }

    return false;  //불가능
}

void solve() {
    int left = 0;
    int right = MAX;
    int mid = 0;
    while (left <= right) {
        mid = (left + right) / 2;  //옮길 수 잇는 무게
        bool ret = bfs(mid);

        if (ret) {  // 가능
            left = mid + 1;
        } else {
            right = mid - 1;
        }

    }

    cout << right << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    input();
    solve();

    return 0;
}

• bfs + 이분 탐색으로 풀었다.
• 메모리 초과 때문에 고생.. cost[][]로 따로 가중치를 저장 해 뒀는데 여기서 메모리 초과가 나서 vector<pair<int, int>>[]로 바꿔줬다.
• 이분탐색으로 건너갈 수 있는 무게의 최솟값을 구한다.
• 시작점부터 연결 된 곳 까지 반복문을 돌면서, 무게를 넘지 않고, 방문하지 않은 곳을 큐에 넣어주며 반복한다.
• 도착점에 도착 했을 경우 true리턴, 아니라면 false 리턴한다.
• true가 리턴 되면 좀 더 큰 것을 옮겨보고, 아니라면 좀 더 작은 것을 옮겨본다.