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

1. 문제 링크

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

14676번: 영우는 사기꾼?

2. 문제 요약

---

3. 아이디어 정리

1. 우선 위상 정렬을 하기 위해 진입 차수를 아래와 같이 저장한다.

2. 건설을 하는 경우

• 진입 차수가 0이 아니면 치트키 사용
• 0이고 처음 건물을 지은 경우는 다음 연결 관계를 가진 진입 차수를 -1 하여 건물을 짓도록 한다.

3. 파괴하는 경우

• 지은 건물이 지금까지 없는 경우 치트키 사용
• 그 외의 경우 파괴된 건물이 마지막이면 다음 연결 관계를 가진 진입 차수를 + 1 하여 건물을 못 짓게 한다.

---

4. 문제 풀이

4-1. 내 풀이

import sys

# 건물 종류, 건물 사이 관계, 게임 정보의 개수
n, m, k = map(int, sys.stdin.readline().split())

indegree = [0] * (n + 1)            # 진입차수 
graph = [[] for i in range(n + 1)]  # 연결관계 저장 
now = [0] * (n + 1)                 # 현재 지은 건물 수 
lier_flag = False                   # 영우의 치트키 여부 

for _ in range(m):
    # x를 건설해야 y건설 가능
    x, y = map(int, sys.stdin.readline().split())
    graph[x].append(y)
    indegree[y] += 1    # 진입 차수 > 해당 건물 지어지기 전 기어야할 건물 수 

for _ in range(k):
    # 1:건설, 2 파괴
    n, a = map(int, sys.stdin.readline().split())
    if n == 1:
        if indegree[a] != 0:  # 진입차수 0 아니면 건설 x
            lier_flag = True
            break
        else:
            now[a] += 1   # 지은 건물 수 증가
            if now[a] == 1:   # 처음 건설한 경우 진입차수 -1 를 하여 내 다음 번호가 건물 건설이 가능하도록함
                for next in graph[a]:
                    indegree[next] -= 1

    else:
        if now[a] <= 0:   # 지은 건물이 없는 경우 거짓말
            lier_flag = True
            break
        else:
            now[a] -= 1
            if now[a] == 0:      # 마지막 건물이 파괴된 경우, + 1를 해서 건설을 못하게 진입 차수 증가 
                for next in graph[a]:
                    indegree[next] += 1

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

 

---

5. 결론

• 변형된 위상 정렬 문제이다.