[백준(BOJ)] 14676번 : 영우는 사기꾼? - PYTHON[파이썬]

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

14676번: 영우는 사기꾼?

 

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 구현
• 그래프 이론
• 위상 정렬

 

---

 

⊙ 문제 접근 과정

 

1️⃣ graph[i].append(j), indegree[j]+=1

     m만큼 반복

 

2️⃣ 건물을 K번 짓거나 파괴

 

3️⃣ 1은 건설, 2는 파괴

     1일 시, 선행 건물이 있는지 판별

     2일 시, 건물이 지어졌는지 확인

 

---

 

⊙ 문제 풀이

 

import sys

N, M, K = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(N+1)]
build = [0]*(N+1)
indegree = [0]*(N+1)
flag = False

for _ in range(M):
    i, j= map(int, sys.stdin.readline().split())
    graph[i].append(j)
    indegree[j]+=1

for _ in range(K):
    command, building = map(int, sys.stdin.readline().split())
    if command == 1:
        if indegree[building]:
            flag = True
            break

        build[building]+=1

        if build[building] == 1:
            for i in graph[building]:
                indegree[i]-=1
    else:
        if build[building] <= 0:
            flag = True
            break

        build[building]-=1

        if not build[building]:
            for i in graph[building]:
                indegree[i]+=1

if flag:
    print("Lier!")
else:
    print("King-God-Emperor")

 

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!