[Python] 위상정렬 - 14676. 영우는 사기꾼?(골3)

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

14676번: 영우는 사기꾼?

 

>>문제 포인트

 

1) 건물들은 중복으로 지을 수 있음을 고려

 

2) 치트키를 판단할 수 있는 상황을 잘 확인하여야 함

- 치트키 상황1. 건물 파괴할 때 : 파괴대상인 건물이 안지어져 있을때

- 치트키 상황2. 건물 지을때 : 모든 선행 건물이 안지어져 있을때

 

3) 선행건물의 판단여부(indegree)

- 위상정렬의 indegree 행으로 선행건물 지음 여부를 판단

=> 선행건물 지을 때마다 진입차수에서 빼주기

=> 선행건물이 파괴되면 진입차수 더해주기

 

4) 건물의 개수(built 행)

- 각 건물의 건설 개수를 built 행이 저장함

 

 

v, e, play= map(int, input().split())

graph=[[] for i in range(v+1)]

indegree=[0]*(v+1)

built= [0]*(v+1)

#그래프로 연결 -> a(선행) -> b

#b의 진입차수 1개씩 증가

for _ in range(e):

  a,b= map(int, input().split())

  graph[a].append(b)

  indegree[b]+=1

flag=0

for _ in range(play):

  a,b= map(int, input().split())

  #건물 파괴하기

  if (a==2):

    #치트키 상황1. 건물이 안지어져 있는데 파괴하려 할때

    if built[b]<=0:

      flag=1

      break

    #건물 하나를 파괴

    built[b]-=1

    #파괴한 건물이 마지막 건물이었을 때 -> 진입차수 증가(선행조건이 다시 생김)

    if built[b]==0:      

      for i in graph[b]:

        indegree[i]+=1

#건물 짓기

  else:

    #치트키 상황1. 선행건물이 안지어져 있는데 지으려할 때

    if indegree[b] !=0:

      flag=1

      break

   

    #처음 짓는 것이라면  -> 연결된 건물들의 진입차수 감소

    if built[b]==0:

        for i in graph[b]:

            indegree[i]-=1

    built[b]+=1

if flag==1:

  print('Lier!')

else:

  print('King-God-Emperor')