[백준] 8452 그래프와 쿼리

문제 링크 : www.acmicpc.net/problem/8452

8452번: 그래프와 쿼리

문제 유형

BFS, Dijkstra, 오프라인 쿼리

 

오프라인 쿼리(Offline Query)란, 주어지는 쿼리들을 받는 즉시 처리하지 않고 모두 저장해둔 뒤

임의의 순서로 쿼리를 해결하는 기법을 말한다.

이 문제에서는 모든 쿼리를 다 받은 뒤, 쿼리를 역순으로 처리함으로써 문제를 간단화하여 해결할 수 있다.

 

즉, 원래의 U k 쿼리는 그래프의 k번 간선을 제거하는 것이지만,

이를 역순으로 적용한다면 원래 k번 간선이 없는 그래프에서 k번 간선을 추가하는 것과 같아진다.

따라서 U 쿼리가 존재하는 간선들을 모두 제거한 최초 그래프에서 E 쿼리를 역순으로 실행하며,

U쿼리가 나올 때마다 해당하는 간선을 추가한 뒤 최단거리를 다시 구해주면 된다.

간선이 추가되어도 최단거리는 반드시 늘어나지는 않기 때문에, 이러한 방법으로 구현을 간단화할 수 있다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <memory.h>
 
#define INF 99999999
 
using namespace std;
typedef pair<int, int> p;
 
int n, m, q, dist[1001], answer[200001];
bool edge_not_use[100001];
vector<p> edges, queries;
vector<int> adj[1001];
 
void bfs() {
    for (int i = 1; i <= n; i++) dist[i] = INF;
    queue<int> que;
    que.push(1);
    dist[1] = 0;
 
    while (!que.empty()) {
        int cur = que.front();
        que.pop();
 
        for (int i = 0; i < adj[cur].size(); i++) {
            int nextnode = adj[cur][i];
            if (dist[nextnode] > dist[cur] + 1) {
                dist[nextnode] = dist[cur] + 1;
                que.push(nextnode);
            }
        }
    }
}
 
void set_graph() {
    //U쿼리에 해당하는 간선을 모두 제거한 최초 그래프 구성
    for (int i = 0; i < edges.size(); i++) {
        if (edge_not_use[i]) continue;
        adj[edges[i].first].push_back(edges[i].second);
    }
}
 
void init() {
    int f, s;
    cin >> n >> m >> q;
 
    for (int i = 0; i < m; i++) {
        cin >> f >> s;
        edges.push_back({ f, s });
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    char qtype; int num;
    for (int i = 0; i < q; i++) {
        cin >> qtype >> num;
        if (qtype == 'U') {
            edge_not_use[num - 1] = true;
            queries.push_back({ 1, num - 1 });
        }
        else queries.push_back({ 0, num });
    }
 
    set_graph();
    bfs();
 
    int idx = 0;
    for (int i = queries.size() - 1; i >= 0; i--) {
        if (queries[i].first == 1) {    //간선 추가
            p e = edges[queries[i].second];
            adj[e.first].push_back(e.second);
 
            //가지치기 : 최단거리가 갱신되지 않을 것을 안다면 bfs를 건너뜀
            if (dist[e.second] <= dist[e.first] + 1) continue;    
 
            bfs();
            continue;
        }
        if (dist[queries[i].second] == INF) answer[idx++] = -1;
        else answer[idx++] = dist[queries[i].second];
    }
 
    for (int i = idx - 1; i >= 0; i--) printf("%d\n", answer[i]);
 
    return 0;
}