[C++] 백준 2307번: 도로검문

🔗 문제

2307번: 도로검문

2307번: 도로검문

 

🖍 풀이

문제를 하나씩 뜯어보면 일단 범죄자의 도주 경로와 최소 비용을 구해야 한다.

• 경로는 양의 가중치가 있는 그래프로 주어진다.
• 시작 지점과 도착 지점이 주어진다.

두 조건을 보아 다익스트라 기법을 이용해야 한다는 감을 잡았다.

 

어려웠던 점

최대 지연을 위해서는 모든 도로를 다 빼는 건 시간 초과에다가 틀린 접근이다.( 당ㅇ연함)

도주 경로의 도로를 빼야한다는건 알았는데 어떻게 구현할지 모르겠어서 인터넷의 도움을 받았다.

 

 

dijkstra(isCriminal, from, to)

• isCriminal : 범죄자의 도주 경로를 구하는 중이면 true
  • true: 현재 노드가 x일 때 parent[x]에 이전 노드를 저장한다.
• from, to: 지연 시킬 도로 from-to를 표현
  • 지연 시킬 도로에 해당하면 이동 불가하게 만든다. (코드 참고)

 

최대 지연시킬 수 있는 도로 찾기

int max_time= 0;
parent[1] = 1; // 출발점이라서 자기 자신이 부모다. 

for(int i=N; i!=parent[i]; i=parent[i])
{
    max_time = std::max(max_time, dijkstra(false, i, parent[i]));
    if(max_time == INF) break;
}

• 범죄자의 도주 경로를 역순으로 도로를 점거 하여 최소 이동거리를 구한다.
  • 만약 도주 경로가 1-2-3-7이라면
    • 7-3, 3-2, 2-1 이 순서로 도로를 이동하지 못하게 하고 탐색한다.
• 역순으로 진행하다가 부모가 자기 자신인 1을 만나면 종료된다.
• 도주 경로에 있는 도로가 유일한 탈출 경로라면 max_time은 INF다.
  • 도둑 탈출 불가 루트 찾음 → 정답 : -1

 

💾  소스

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

const int INF = 987654321;

int N, M;

std::vector<int> parent;
std::vector<std::pair<int, int>> W[1001];

int dijkstra(bool isCriminal = false, const int from = -1, const int to = -1)
{
    std::priority_queue<std::pair<int, int>> pq;
    
    std::vector<int> distance (N+1, INF);
    distance[1] = 0;
    
    pq.push({0, 1}); // cost, node
    while(!pq.empty())
    {
        int cost = -pq.top().first;
        int node = pq.top().second;
        pq.pop();
        
        if(cost > distance[node])
            continue;
        
        for(int i=0; i<W[node].size(); ++i)
        {
            int next_node = W[node][i].first;
            int next_cost = W[node][i].second + cost;
            
            if(next_cost >= distance[next_node]) continue;

            
            if(isCriminal)
                parent[next_node] = node;

            if(from == node && to == next_node) continue;
            if(from == next_node && to == node) continue;

            distance[next_node] = next_cost;
            pq.push({-next_cost, next_node});
        }
    }
    return distance[N];
}

int main()
{
    int a, b, t;

    std::cin >> N >> M;

    parent.resize(N+1, -1);
    for(int i=0; i<M; ++i)
    {
        std::cin >> a >> b >> t;
        
        W[a].push_back({b, t});
        W[b].push_back({a, t});
    }
   
    int criminal_time = dijkstra(true);
    int max_time= 0;
    
    parent[1] = 1;
    for(int i=N; i!=parent[i]; i=parent[i])
    {
        max_time = std::max(max_time, dijkstra(false, i, parent[i]));
        if(max_time == INF) break;
    }
    std::cout << (max_time == INF ? -1 : max_time - criminal_time);
    
    return 0;
}