BOJ 14676 - 영우는 사기꾼? [C++]

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

14676번: 영우는 사기꾼?

문제 요약

건물을 정점으로 본 방향그래프가 주어진다. 각 건물은 건설하거나 파괴될 수 있다. (중복 건설도 가능하다.)건물들 사이의 관계를 나타내는 방향 간선이 주어진다. 간선 $X \rightarrow Y$는 건물 $X$가 건설된 상태여야 건물 $Y$가 건설될 수 있다는 의미이다.$K$개의 작업이 주어지며, 각 작업은 건물 $a$를 건설하거나 파괴하는 것이다.이 $K$개의 작업을 하는 동안, 건설할 수 없는 건물이 건설되거나 건설한 적 없는 건물이 파괴되는 경우가 있는지 판별해야 한다.

 

문제 해결

건물들 사이의 관계를 나타낸 방향그래프에서, 건물 $a$를 지을 수 있다는 것은 $a$를 짓기 위해 필요한 모든 건물들이 이미 건설된 상태여야 한다는 것이다.

 

초기에는, 그래프에서 진입 차수가 $0$인 건물들만 건설할 수 있다. 다른 건물들은 그 건물을 끝으로 하는 간선들에 대해, 그 시작점의 건물들이 모두 지어져야 건설할 수 있다.

즉, 각 건물들의 진입 차수 배열을 관리하면 건설 가능 여부를 $O(1)$에 확인할 수 있다.

 

건설 작업이 들어오면, 먼저 진입 차수가 $0$인지 확인한다.

$0$이라면, 이 건물과 연결된 모든 간선을 타고 가서 해당 건물의 진입 차수를 1씩 낮춰준다.

이것은 곧 이 건물이 건설되었음을 알리는 행위이다. (중복 건설의 경우에는 낮추면 안 된다.)

$0$이 아니면, 건설할 수 없다는 의미이므로 더 볼 필요없이 프로그램을 종료하면 된다.

 

파괴 작업이 들어오면, 이 건물이 건설되어있는 개수를 확인한다. (적절히 배열로 관리할 수 있다.)

건설된 적이 있다면, 개수를 1 낮춰주고 만약 이번 파괴로 이 건물이 아예 사라졌다면(개수가 1이었다면), 다시 제약을 추가해야 하므로 연결된 간선을 타고 가서 모든 진입 차수를 다시 1씩 올려준다.

건설된 적이 없다면, 있을 수 없는 작업이므로 프로그램을 종료하면 된다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int N, M, K;
    cin >> N >> M >> K;
    int deg[100001]{};
    int build[100001]{};
    vector<vector<int>> V(100001);
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        V[a].push_back(b);
        deg[b]++;
    }
    bool ans = 1;
    for (; K--;) {
        int a, b;
        cin >> a >> b;
        if (a == 1) {
            if (deg[b]) { cout << "Lier!"; return 0; }
            if (build[b]++)	continue;
            for (int i : V[b])	deg[i]--;
        }
        else {
            if (!build[b]) { cout << "Lier!"; return 0; }
            if (!(--build[b])) {
                for (int i : V[b])	deg[i]++;
            }
        }
    }
    cout << "King-God-Emperor";


}