[Algorithm]Baekjoon 1939번 :: 중량제한

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
struct Node
{
    int ireland;
    int weight;
};
 
struct cmp
{
    bool operator() (const Node& a, const Node& b)
    {
        return a.weight < b.weight;
    }
};
 
int n, m;
vector<vector<Node>> graph;
int maxWeights[10001] = { 0 };
int start, dest;
 
void dij()
{
    priority_queue < Node, vector<Node>, cmp> pq;
    pq.push({ start,0x3f3f3f3f });
    maxWeights[start] = 0;
 
    while (!pq.empty())
    {
        int curNum = pq.top().ireland;
        int curWeight = pq.top().weight;
        pq.pop();
 
        if (curWeight < maxWeights[curNum]) continue;
 
        for (int i = 0; i < graph[curNum].size(); ++i)
        {
            int nextIreland = graph[curNum][i].ireland;
            int nextWeight = min(curWeight, graph[curNum][i].weight);
 
            if (maxWeights[nextIreland] < nextWeight)
            {
                maxWeights[nextIreland] = nextWeight;
                pq.push({ nextIreland, nextWeight });
            }
        }
    }
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
 
    graph.resize(n+1);
 
    for (int i = 0; i < m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
 
        graph[a].push_back({ b,c });
        graph[b].push_back({ a,c });
    }
 
    cin >> start >> dest;
 
    dij();
    
    cout << maxWeights[dest];
}
 
 

 

처음에 문제이해하는데에 있어서 살짝 헤맸던 문제.

 

평범한 양방향 그래프가있고, 최소 한개의 경로는 반드시 존재하는 출발지와 도착지가 있다.

출발지에서 출발할 때, 인접해있는 간선이 여러개 있다면 아래의 조건에 맞는 간선만 선택 가능하다.

 

=> 이때까지 선택했던 간선의가중치값보다 이하인 가중치를 가진 간선.

 

A, B, C가 있고 출발지가 A, 도착지가 C라고 가정해보자.

A에서 B를 잇는 다리는 300의 무게를 견딜 수 있다. 그러나 B->C는 200밖에 못견딘다.

'한번의 이동'으로 도착지까지 갈 수 있어야하기 때문에, 출발지인 A에서부터 200을 들고가야한다. 

그래야 C까지 한번에 도착할 수 있다. (300을 들고 출발했다가 B에서 100을 덜어낸다던가하는 경우는 없다.)

 

즉, 우리는 이전에 선택했던 가중치값보다 더 작은 가중치를 지닌 간선을 선택해야만 한다.

이 때, 도착지까지 갈 때의 경로는 무수히 많을 것이고 최종적으로 이 작은가중치들을 선택한것들 중에 최대값을 구해야 한다.

 

 

처음 풀이는 그냥 가중치순으로 내림차순 정렬한다음에 완탐해서 첫 도착한게 정답이지 않나? 했는데 틀렸었다.

아래와 같은 케이스가 있기 때문이다.

 

// input
4 4
1 2 100
2 3 1
3 4 10
1 3 10
1 4

// ans
10

// wrong output
1

 

 

 

그래서 기본적인 다익스트라에서 조건을 변경해서 풀었다.

결국 최대값을 구해야 하니, 우선순위큐에서 꺼내는 조건을 가중치최대값으로 설정했다.

값을 업데이트하기위한 조건에서는 문제에서 설명했듯이 현재까지 선택했던 값들보다 더 작은 간선을 선택해야 다음 섬으로 갈 수 있으니, min(curWeight, nextWeight)로 하고, dp테이블에 기록되어있는 값과 비교해줬다.