[BOJ] 백준 14676번 문제 풀이 (Python)

1. 문제 풀이

배열을 응용해서 문제를 풀었습니다.

• $building[i]$: 건물 $i$의 갯수
• $graph[i]$: $i$를 건설하기 위해 필요한 건물 목록
• 건물 $i$를 건설할 때 $graph[i]$에 있는 건물들이 모두 건설되어있지 않으면 Lier!
• 건물 $i$를 파괴할 때 $building[i]$가 0이면 Lier!

2. 코드

import sys
def input(): return sys.stdin.readline().rstrip()

n, m, k = map(int, input().split())
buildings = [0] * (n+1)
graph = [[] for _ in range(n+1)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[b].append(a)

possible = True
for _ in range(k):
    a, b = map(int, input().split())
    if a == 1:
        for prev in graph[b]:
            if not buildings[prev]:
                possible = False
        if possible:
            buildings[b] += 1
    else:
        if not buildings[b]:
            possible = False
        if possible:
            buildings[b] -= 1
if possible:
    print("King-God-Emperor")
else:
    print("Lier!")