[Algorithm]Baekjoon 1800번 :: 인터넷 설치

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

1800번: 인터넷 설치

struct Node
{
    int node;
    int price;
};
 
struct cmp
{
    bool operator() (const Node& a, const Node& b)
    {
        return a.price > b.price;
    }
};
 
 
int n, p, k;
int dist[1001];
vector<vector<Node>> graph(1001);
 
bool check(int standard)
{
    memset(dist, 0x3f, sizeof(dist));
 
    priority_queue<Node, vector<Node>, cmp> pq;
    dist[1] = 0;
    pq.push({ 1,0 });
 
    while (!pq.empty())
    {
        int curNode = pq.top().node;
        int curPrice = pq.top().price;
        pq.pop();
 
        if (dist[curNode] < curPrice) continue;
 
        for (int i = 0; i < graph[curNode].size(); ++i)
        {
            int nextNode = graph[curNode][i].node;
            int nextPrice = graph[curNode][i].price;
            int result = curPrice;
 
            if (nextPrice <= standard) result += 0;
            else result += 1;
 
            if (result < dist[nextNode])
            {
                dist[nextNode] = result;
                pq.push({ nextNode,result });
            }
        }
    }
 
    return dist[n] <= k;
}
 
 
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> p >> k;
 
    for (int i = 0; i < p; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
 
        graph[a].push_back({ b,c });
        graph[b].push_back({ a,c });
    }
 
    int answer = -1;
    int left = 0;
    int right = 1e6;
 
    while (left <= right)
    {
        int mid = (left + right) / 2;
 
        if (check(mid))
        {
            right = mid - 1;
            answer = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
 
    cout << answer;
 
    return 0;
}

아마 처음 풀어본 결정문제(Decision Probelm)인 것 같다. 

문제만 읽어보면 어떠한 일련의 로직을 거쳐 해를 구해야 하는 것 같다.

하지만 이 값을 구하기 위해서 완전탐색을 하면 시간제한에 걸린다. 

사실 골드1짜린데 완전탐색으로 풀리면 골드4짜리정도 문제겠지...

 

그래서 문제를 재해석 한다. 처음부터 정답값을 정해놓고, 이 값이 유효한지 안유효한지만 체크하고(true or false), 유효하다면 점점 그 값을 낮춰본다. (지불할 최소의 비용을 구해야하니까)

 

여기서 '유효하다'는 의미가 중요한데, 예를들어 5000이라는 값을 딱 정해놓고, 실제로 1번부터 n번노드까지 탐색했을 때 

원장이 최소로 낼 비용이 5000이 될 수 있는지 검사하여, 가능할 경우 유효하다..라는 뜻이다.

 

그리고 그걸 알기위해서 다익스트라를 수행할건데, 해당값이 최소비용이 되려면 해당비용을 초과하는 인터넷선의 개수가 k개를 넘어선 안된다. k개까지는 무료로 제공받을 수 있기 때문이다.

그렇기 때문에 기준으로 잡은 값(5000)이하의 인터넷선에 대해서는 0의 가중치를 부여하고, 초과하는 인터넷선에 대해서는 1의 가중치를 부여한다. 

다익스트라를 마친 후, dist[n]의 값이 k개 이하라면 true를 리턴, 아니라면 false를 리턴한다.

k개 이하라는 것은, n번 노드까지 가는데에 기준으로 잡은값을 초과하는 인터넷선 개수가 k개 이하라는 것이다.

k개 이하라는것은 결국 전부 무료로 제공받을 수 있는 개수이기 때문에 이 5000이라는 값은 유효한 값이 된다.

 

 

그리고 이 '값'을 이분탐색으로 결정한다. 한 간선당 최대가중치는 1000000이기 때문에 right는 1000000으로 잡고 이분탐색을 수행한다.

 

최소의 값을 뽑는것이기 때문에, mid값이 유효한지 체크를 할 건데, 유효한 값이면 값을 더 줄일 수 있는 가능성이 있기 때문에 right를 감소시키고, 유효하지 않다면 left값을 증가시킨다.

 

참고한 글

https://justicehui.github.io/usaco/2019/07/12/BOJ1800/

백준1800 인터넷 설치