[BFS]백준1939번 중량제한

백준 1939번

중량제한

처음에는 구조체를 이용해 BFS만으로 해결하려 했다.

답은 제대로 나오는 것 같았지만 코드를 작성하면서도 스스로 예상했던 메모리 초과가 떴다.

이 문제가 BFS만으로 해결하기 어려운 이유는 중복을 (방문한 곳)을 처리하는 방법이 단순하지가 않기 때문이다.

일반적으로 BFS 문제에서는 한 번 방문한 곳은 방문하지 않고, 목표로 하는 노드를 방문하는 경우 종료되지만 이 문제에서는

1. 정답까지 가는 경로가 여러 개이고, 한 번 목적지를 도착했다고 해서 (경로를 하나 찾았다고 해서) 끝나는 것이 아니기 때문이다.
2. 각 노드에 도착했을 때 현재까지의 최소 제한 중량은 얼마인지, 각자 어떤 노드들을 거쳐 여기까지 왔는지를 알고 있어야 한다.

단순 BFS로는 이 문제를 해결할 수가 없다. (있긴 하지만, 시간복잡도나 공간복잡도를 고려했을 때 적절하지 않다.)

우선, 문제의 지시사항을 다시 살펴보자.

우리에게 구하도록 하는 것은 한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값이다.

이 말은, 각 경로의 최소 제한 중량들 중에서 최댓값이 무엇인지를 물어보는 것이다.

왜냐하면, 한 경로에서 이동할 수 있는 물품의 최대 중량은 가장 중량제한이 낮은 다리보다 클 수 없기 때문이다.

우리에게는 중량들이 입력으로 주어지고, 정답은 중량들 사이에 있기 때문에 그 안에서 정답을 찍고, 찍은 정답이 경로를 통과할 수 있는지 아닌지 알아야 한다.

정답을 찍는 가장 좋은 방법 중 하나는 이분 탐색을 이용하는 것이다.

들어올 수 있는 중량의 범위는 1 ~ 1,000,000,000 이다.

따라서 left를 1, right 를 1,000,000,000로 두고 이분 탐색을 시작한다.

mid 값은 (left + right) / 2 가 된다.

mid 값을 이용해 bfs를 수행한다.

만약 bfs를 통해 어떤 경로든 목적지에 도착을 할 수 있다면, 해당 mid 값보다 더 큰 중량값을 찾아보기 위해 left를 mid + 1 로 증가시켜 mid 값을 증가시킨다.

만약 bfs를 통해 어떤 경로로도 목적지에 도착을 할 수 없다면, 해당 mid 값보다 더 작은 중량값을 찾아보기 위해 right를 mid -1로 감소시켜 mid의 값을 감소시킨다.

BFS 에서는 queue에 push 하는 조건을 visited 외에 한 가지를 더 두어야 하는데, 현재 넘으려는 다리의 용량이 내가 찍은 값보다 같거나 큰 경우에만 통과하게 한다.

위의 과정을 left 가 right과 같아질 때까지만 반복한다.

구조체를 이용한 코드 (메모리 초과 됨)

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

struct island{
    int num;
    long long weight;
    bool visited[10001];
};
// adjacent and weight
bool visited[10001][10001];
// vector<long long> answer;
long long answer;

int main(){
    int N,M;
    cin >> N >> M;
    vector<vector<pair<int,long long> > > adj(N+1);
    vector<bool> settings(N+1,false);

    // for(int i=0;i<N;i++){
    //     struct island tmp;
    //     tmp.weight = 0;
    //     memset(tmp.visited,false,sizeof(tmp.visited));
    // }

    for(int i = 0; i < M ; i++){
        int island1,island2;
        long long weight;
        cin >> island1 >> island2 >> weight;

        adj[island1].push_back(make_pair(island2,weight));
        adj[island2].push_back(make_pair(island1,weight));
    }
    int start, dst;
    cin >> start >> dst;
    // island, sum
    
    queue<struct island> q;
    struct island tmp;
    tmp.num = start;
    tmp.weight = 1000000001;
    tmp.visited[start] = true;
    memset(tmp.visited,false,sizeof(tmp.visited));
    q.push(tmp);

    while(!q.empty()){
        struct island cur = q.front();
        q.pop();
        if(cur.num == dst){
            // answer.push_back(cur.weight);
            answer = answer < cur.weight ? cur.weight : answer;
        }
        else{
            for(int i=0;i<adj[cur.num].size();i++){
                if(!cur.visited[adj[cur.num][i].first]){
                    struct island tmp;
                    tmp.weight = cur.weight > adj[cur.num][i].second ? adj[cur.num][i].second : cur.weight;
                    tmp.num = adj[cur.num][i].first;
                    memcpy(tmp.visited,cur.visited,sizeof(cur.visited));
                    tmp.visited[cur.num] = true;
                    q.push(tmp);
                }
            }
        }
    }
    cout << answer;
}

이분탐색 + bfs를 이용한 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;
vector<vector<pair<int,int> > > adj(10001);
int start, dst;
bool bfs(int n);
int main(){
    int N,M;
    cin >> N >> M;

    for(int i=0;i<M;i++){
       int island1, island2;
       long long weight;
       cin >> island1 >> island2 >> weight;
       adj[island1].push_back(make_pair(island2,weight));
       adj[island2].push_back(make_pair(island1,weight));
    }
    cin >> start >> dst;
    int answer = 0;
    int left = 1, right = 1000000000;
    while(left<=right){
        int mid = (left + right)/2;
        //도달 가능, 정답 갱신 
        if(bfs(mid)){
            if(answer < mid){
                answer = mid;
            }
            left = mid + 1;
        }else{ // 도달 불가능
            right = mid - 1;
        }
    }
    cout << answer << endl;
    return 0;
}

bool bfs(int n){
    bool visited[10001] = {false,};
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while(!q.empty()){
        int cur = q.front();
        q.pop();
        if(cur == dst){
            return true;
        }

        for(int i=0;i<adj[cur].size();i++){
            if(!visited[adj[cur][i].first] && adj[cur][i].second >= n){
                q.push(adj[cur][i].first);
                visited[adj[cur][i].first] = true;
            }
        }
    }
    return false;
}