14676번: 영우는 사기꾼?
프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐
www.acmicpc.net
문제
영선이와 영우는 최근 ‘우주전쟁’ 이라는 게임을 시작했다. ‘우주전쟁’은 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번째 건물이 지어진 개수 저장
영우의 게임 정보를 입력받으며 영우가 치트키를 사용했는지 확인해본다.
- 건설
- indegree[b]에는 선행되어야 하는 건물의 개수가 저장되어 있는데 선행되어야 하는 건물이 건설될 때마다 1씩 감소시켜주므로 indegree[b]==0일 때 건물의 건설이 가능하다. 0이 아닌데 건물을 건설한 게임 정보가 들어온다면 영우가 치트키를 쓴 것이라고 볼 수 있다.
- 영우가 정상적으로 건물을 건설했다면 builing[b]를 1 증가시켜준다. 이때 building[b] == 1이라면 건물이 없다가 생겨난 것이므로 영향을 미치는 건물들의 indegree 값을 1 감소시킨다.
- 파괴
- building[b] <= 0이라면 건설 정보에 없는 건물, 즉 치트키로 지어진 건물을 파괴했다는 말이다.
- 정상적으로 건물을 파괴한 경우 builing[b] 값을 1 감소시켜준다. 이때 building[b] == 0이 된다면 b번 건물이 하나도 없다는 말이므로 b번 건물이 영향을 미치는 건물들의 indegree를 1씩 증가시켜준다.
'문제풀이 > 위상정렬' 카테고리의 다른 글
[Python/파이썬] 백준 9470번 Strahler 순서 (1) | 2023.12.07 |
---|---|
[Python/파이썬] 백준 21276번 계보 복원가 호석 (0) | 2023.10.16 |
[Python/파이썬] 백준 2056번 작업 (0) | 2023.05.17 |
[Python/파이썬] 백준 1766번 문제집 (0) | 2023.04.01 |
[Python/파이썬] 백준 2623번 음악프로그램 (0) | 2023.04.01 |