[Atcoder] ABC305 :: E - Art Gallery on Graph

약간의 테크닉이 필요한 그래프 탐색 문제였다.

그래프가 주어지고, K개의 특별한 노드가 주어진다. 이 특별한 노드는 가드가 존재하는데, 이 가드는 자신과의 거리가 h 미만인 노드들을 지킬 수 있다는 상황이 주어진다. 이때 가드에 의해 보호받을 수 있는 노드의 총 개수와 번호를 출력해야 하는 문제이다.

그래서 나는 다익스트라로 문제를 접근했다.
가드가 지키고 있는 노드들을 전부 우선순위 큐에 때려박고, 순차적으로 탐색을 할 것이다. 이때 우선순위 큐에서 꺼내는 정렬 기준은 '남은 h의 크기'로 잡았다.

왜냐하면 초기 K에 속하지 않는 어떤 P라는 노드가 있다고 가정해보자. 이 P라는 노드에 도달할 수 있는 방법은 여러가지가 존재할 수도 있는데, 우리는 이 P라는 노드에 도달할 수 있으면서 h가 가장 크게 남아있는 경우만 찾으면 된다. 그 이외의 값들은 가장 큰 h에 의해 무시해도 되기 때문이다.

이러한 로직으로 접근을 해봤을때 각 노드는 딱 한번만 접근하고 모든 간선을 한번씩 타지만, 방문을 표시하는 부분 때문에 간선의 개수는 M개를 넘어서게 되고, O((N+M) log(N+M))에 해결할 수 있다.

주의할 점은 방문을 언제 표시할 것인가? 이다. 
나는 방문을 표시할 순간을 잘못 나타내서 풀지 못했는데, 이 부분만 조금 유의해서 생각해보면 크게 어렵지 않은 문제였다.

#include<iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define X first
#define Y second
#define NUM 200010
using namespace std;
typedef pair<int, int> pii;
int N, M, K;
bool visited[NUM];
vector<int> adj[NUM];
priority_queue<pii> pq;

int main() {
    memset(visited, false, sizeof(visited));
    cin >> N >> M >> K;
    
    for (int i=0; i<M; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    
    for (int i=0; i<K; i++) {
        int p, h;
        cin >> p >> h;
        pq.push({h, p});
    }
    
    while (!pq.empty()) {
        auto curr = pq.top();
        pq.pop();
        if (curr.X < 0 || visited[curr.Y]) continue;
        visited[curr.Y] = true;
        for (int next: adj[curr.Y]) {
            if(visited[next]) continue;
            pq.push({curr.X - 1, next});
        }
    }
    int cnt = 0;
    for (int i=1; i<=N; i++) {
        if (visited[i]) cnt++;
    }
    cout << cnt << '\n';
    for (int i=1; i<=N; i++) {
        if (visited[i]) {
            cout << i << ' ';
        }
    }
}