[Python/파이썬] 백준 14676번 영우는 사기꾼?

14676번: 영우는 사기꾼?

 

문제

영선이와 영우는 최근 ‘우주전쟁’ 이라는 게임을 시작했다. ‘우주전쟁’은 1대1로 하는 RTS(실시간 전략 게임) 게임으로, 각 플레이어는 건물을 건설하고, 건물에서 유닛을 생성하여 싸운다. ‘우주전쟁’은 건물을 짓는 순서가 정해져 있는데, 예를 들어 건물들이 다음과 같은 관계도를 가진다고 할 때,

2, 3번 건물은 반드시 1번 건물이 건설된 상태여야 지어질 수 있고, 4번 건물은 반드시 2, 3번 건물이 건설된 상태여야 지어질 수 있다. 단 4번 건물은 1번 건물과는 직접적인 연관이 없기 때문에 1번 건물이 없다고 하더 라도 4번 건물은 건설이 가능하다. 이때 1번 건물은 2, 3번 건물에 영향을 미친다고 할 수 있고, 2, 3번 건물은 4번 건물에 영향을 미친다고 할 수 있다. 또한 모든 건물들은 중복 건설이 가능하다. ‘우주전쟁’ 게임의 제작사 인 ‘얼음폭풍’사는 게임의 밸런스를 유지하기 위해 한 건물은 최대 3개의 건물에게만 영향을 미치도록 하였다. 또 ‘우주전쟁’ 게임에는 치트키가 하나 있는데, 이 치트키를 사용하면 원하는 건물을 마음대로 설치할 수 있다. 하지만 이 치트키를 사용하면 너무나 쉽게 게임에서 이길 수 있기 때문에 영선이와 영우는 서로 치트키를 쓰 지 않기로 약속했다. 하지만 이상하게도 영우는 영선이와의 게임에서 모두 승리하였고, 그런 영우를 이상하게 여긴 영선이는 영우의 건물 건설/파괴 정보를 가져왔다. (치트키로 건설한 건물은 건설 정보에 들어가지 않는 다.) 영우의 게임정보를 보고 영우가 치트키를 사용했는지 판단하는 프로그램을 만들어 영선이를 도와주자.

입력

프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 건물의 관계인 X Y 가 차례대로 중복 없이 주어진다. (X를 건설해야 Y를 건설할 수 있음.) (1 ≤ X, Y ≤ N) 다음 줄부터 K줄에 걸쳐 영우의 게임 정보가 다음과 같이 주어진다. (1 ≤ a ≤ N)

• 1 a(영우가 a번 건물을 1개 건설함)
• 2 a(영우의 a번 건물이 1개 파괴됨)

출력

프로그램의 출력은 표준 출력으로 한다. 영우가 정상적으로 건물을 건설하거나, 건설한 만큼의 건물만 파괴되 었다면 ‘King-God-Emperor’를. 건설할 수 없는 건물을 건설하거나, 건설한적 없는 건물이 파괴되었다면 ‘Lier!’ 를 출력하자.

코드

처음에는 아래와 같이 풀었다가 86퍼쯤에서 시간 초과가 발생했다. 

아마 한 건물은 최대 3개의 건물에게만 영향을 미칠 수 있다고 했지만 반대로 선행되는 건물의 개수에 대한 조건은 없었기 때문인 것으로 생각된다. 

 

시간 초과 발생 코드

import sys
input = sys.stdin.readline
from collections import defaultdict

n, m, k = map(int, input().split())
# 건물 관계
relation = [[] for _ in range(n+1)]
for _ in range(m):
    x, y  = map(int, input().split())
    relation[y].append(x)   # x를 건설해야 y 건설 가능
    
# 영우의 게임 정보
building = defaultdict(int)
for _ in range(k):
    a, b = map(int, input().split())
    if a == 1:  # 건설
        # 선행 건물 모두 건설되었는지 확인
        for prev in relation[b]:
            if building[prev] <= 0:
                print("Lier!")
                exit()
        building[b] += 1
    else:   # 파괴
        if building[b] <= 0:    # 건설 정보에 없는 건물 파괴
            print("Lier!")
            exit()
        building[b] -= 1
        
print("King-God-Emperor")

 

그래서 아래와 같이 위상 정렬을 이용하여 풀이하였다. 

 

정답 코드

import sys
input = sys.stdin.readline

n, m, k = map(int, input().split())
# 건물 관계
relation = [[] for _ in range(n+1)]
indegree = [0] * (n+1)  # i번째 건물을 짓기 위해 선행되어야 하는 건물 수
for _ in range(m):
    x, y  = map(int, input().split())
    relation[x].append(y)   # x를 건설해야 y 건설 가능
    indegree[y] += 1
    
# 영우의 게임 정보
building = [0] * (n+1)  # i번째 빌딩 개수
for _ in range(k):
    a, b = map(int, input().split())
    if a == 1:  # 건설
        if indegree[b] > 0:    # 선행되어야 하는 건물이 모두 건설되지 않았는데 건설
            print("Lier!")
            exit()
        building[b] += 1
        if building[b] == 1:    # b번 빌딩이 없다가 지어진 경우
            for nx in relation[b]:  # 다음 건물들 진입 차수 감소
                indegree[nx] -= 1
    else:   # 파괴
        if building[b] <= 0:    # 건설 정보에 없는 건물 파괴
            print("Lier!")
            exit()
        building[b] -= 1
        if building[b] == 0:    # 건물 파괴하니 하나도 없는 경우
            for nx in relation[b]:
                indegree[nx] += 1
        
print("King-God-Emperor")

 

• relation : i번째 건물이 영향을 미칠 수 있는 건물들의 리스트를 저장
• indegree : i번째 건물을 건설하기 위해 먼저 지어져야 하는 건물 개수를 저장. 
• building : i번째 건물이 지어진 개수 저장

영우의 게임 정보를 입력받으며 영우가 치트키를 사용했는지 확인해본다.

1. 건설 
   • indegree[b]에는 선행되어야 하는 건물의 개수가 저장되어 있는데 선행되어야 하는 건물이 건설될 때마다 1씩 감소시켜주므로 indegree[b]==0일 때 건물의 건설이 가능하다. 0이 아닌데 건물을 건설한 게임 정보가 들어온다면 영우가 치트키를 쓴 것이라고 볼 수 있다.
   • 영우가 정상적으로 건물을 건설했다면 builing[b]를 1 증가시켜준다. 이때 building[b] == 1이라면 건물이 없다가 생겨난 것이므로 영향을 미치는 건물들의 indegree 값을 1 감소시킨다.
2. 파괴
   • building[b] <= 0이라면 건설 정보에 없는 건물, 즉 치트키로 지어진 건물을 파괴했다는 말이다.
   • 정상적으로 건물을 파괴한 경우 builing[b] 값을 1 감소시켜준다. 이때 building[b] == 0이 된다면 b번 건물이 하나도 없다는 말이므로 b번 건물이 영향을 미치는 건물들의 indegree를 1씩 증가시켜준다.