[백준 14676] 영우는 사기꾼?

1. 문제 이해

영선이 & 영우 우주전쟁 : 각 플레이어는 건물을 건설하고 건물에서 유닛을 생성하여 싸우는 게임.

'우주전쟁'은 건물을 짓는 순서가 정해져있음.

2,3 건물은 1번 건물이 건설된 상태여야 지어질 수 있음

단, 4번 건물은 1번과는 직접적인 연관 없어서 1번 건물 없어도 4번 건물 건설 가능하다.

 

영우가 영선이한테 다 이김.

영선이가 이상하게 생각함.

영우의 건물 건설/파괴 정보를 가져와 치트키를 사용했는지 판단하는 프로그램 만들어 영선이 돕자.

 

- 입력

건물 종류 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보 개수 K

M줄에 걸쳐 건물 관계 X Y가 중복없이 주어짐(X 건설해야 Y 건설 가능)

K줄에 걸쳐 영우의 게임 정보 다음과 같이 주어짐.

• 1 a (영우가 a번 건물을 1개 건설함) 
• 2 a (영우가 a번 건물을 1개 파괴됨)

- 출력

영우 정상적으로 건물 건설 or 건설한 만큼만 파괴됐으면 'King-God Emperor' 출력

건설할 수 없는 건물 건설 or 건설한 적 없는 건물이 파괴됐으면 'Lier!' 출력

 

2. 조건

- 모든 건물들은 중복 건설이 가능

- 한 건물은 최대 3개의 건물에게만 영향을 미치도록 함.

- 치트키(원하는 건물을 마음대로 설치)가 있음

 

3. 풀이

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
using namespace std;

#define MAX 100001
int n, m, k, x, y, num, node;
vector<int> edge[MAX];
int in_degree[MAX]; //기존
int woo[MAX]; //영우

int main() {
    cin >> n >> m >> k;

    while (m--) {
        cin >> x >> y;
        edge[x].push_back(y);
        in_degree[y]++;
    }

    bool isTrue = true;
    while (k--) {
        cin >> num >> node;

        if (num == 1) { //생성
            if (in_degree[node] == 0) {
                woo[node]++;
                if (woo[node] == 1) { //처음 만든 정점일 때
                    for (auto next: edge[node]) {
                        in_degree[next]--;
                    }
                }
            } else {
                isTrue = false;
            }
        } else { //파괴
            if (woo[node] > 0) {
                woo[node]--;
                if (woo[node] == 0) { // 여기부분 어ㅠ
                    for (auto next: edge[node]) {
                        in_degree[next]++;
                    }
                }
            } else { // 치트키 써서 세운 건물을 파괴하려함
                isTrue = false;
            }
        }
    }
    if (isTrue) {
        cout << "King-God-Emperor";
    } else {
        cout << "Lier!";
    }

    return 0;
}