[백준] 영우는 사기꾼?

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

14676번: 영우는 사기꾼?

필요한 건물이 다 지어졌는지를 체크하기 위한 in_node와 현재 건물의 개수에 대한 정보를 가지고 있는 building_cnt 배열을 활용하여 풀이하였습니다. 건물이 새로 하나 생기는 경우에 해당 건물에 영향을 받는 건물의 in_node를 1 감소시키고 건물이 하나도 없어지는 경우에는 해당 건물에 영향을 받는 건물의 in_node를 1 증가시켜주어야합니다. 그리고 빌딩이 하나도 없는데 없어지거나 필요한 건물이 다 안지어졌는데 짓는 경우에는 치트키를 사용한 경우이므로 Lier를 출력해주면 됩니다. 

 

import sys
from collections import defaultdict, deque

sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

n, m, k = tuple(map(int, input().split()))

building_cnt = [0] * (n + 1)
in_node = [0] * (n + 1)

graph = defaultdict(list)

for i in range(m):
    fr, to = tuple(map(int, input().split()))
    graph[fr].append(to)
    in_node[to] += 1

for i in range(k):
    cmd, building = tuple(map(int, input().split()))

    # 건물을 짓는 경우
    if cmd == 1:
        # 아직 필요한 건물이 다 안지어졌는데 지어진 경우
        if in_node[building] > 0:
            print("Lier!")
            sys.exit(0)
        building_cnt[building] += 1
        # 건물이 하나 생긴 경우
        if building_cnt[building] == 1:
            for nxt in graph[building]:
                in_node[nxt] -= 1

    # 건물을 없애는 경우
    else:
        if building_cnt[building] <= 0:
            print("Lier!")
            sys.exit(0)
        building_cnt[building] -= 1
        # 남아 있는 건물이 없는 경우
        if building_cnt[building] == 0:
            # in_node를 다시 증가 시킨다.
            for nxt in graph[building]:
                in_node[nxt] += 1


print("King-God-Emperor")