[Python] BOJ 14676 - 영우는 사기꾼?

www.acmicpc.net/problem/14676

14676번: 영우는 사기꾼?

앞서 올렸던 위상정렬 알고리즘을 응용해서 푸는 문제이다.

 

 

1. M만큼 X, Y를 입력받고 graph[X]에 Y를 append해주고, indegree[Y]에 1을 더해준다.

2. K만큼 반복문을 돌며 건물을 짓거나 파괴합니다.

3. 만약 command가 1이라면 building번 건물을 짓고자 하는 것이므로 indegree[building]을 확인한다.

  3-1. indegree[building]이 1이상이면 선행조건(먼저 지어야 하는 건물)이 아직 지어지지 않은 것이므로 Lier!를 출력.

  3-2. indegree[building]이 0이하이면 build[building]을 1증가시킨다.   (build배열: building번 건물을 지은 횟수)

        -> building번 건물이 처음 지어진 것이면 building번 건물과 연관된 건물들의 indegree를 1줄여준다.

4. command가 2라면 building번 건물을 파괴하고자 하는 것이므로 build[building]을 확인한다.

  4-1. build[building]이 0 이하이면 파괴할 수 없으므로 Lier! 출력.

  4-2. build[building]이 1이상이면 build[building]을 1감소시킨다.

        -> 만약 build[building]이 0이 되면 다시 지을 때 선행조건을 검사해줘야하므로 building번 건물과 연관된

             건물들의 indegree를 1증가시킨다.

5. 마지막까지 sys.exit(0)에 안 걸리고 돌아가면 "King-God-Emperor" 출력

import sys
input = sys.stdin.readline
N, M, K = map(int,input().split())
graph = [[] for _ in range(N+1)]
build = [0] * (N+1)
indegree = [0] * (N+1)
for _ in range(M):
	X, Y = map(int,input().split())
	graph[X].append(Y)
	indegree[Y] += 1
 
for _ in range(K):
	command, building = map(int,input().split())
	if command == 1:
		if indegree[building]:
			print("Lier!")
			sys.exit(0)
		build[building] += 1
		if build[building] == 1:
			for i in graph[building]:
				indegree[i] -= 1
 
	else:
		if build[building] <= 0:
			print("Lier!")
			sys.exit(0)
		build[building] -= 1
		if not build[building]:
			for i in graph[building]:
				indegree[i] += 1
 
print("King-God-Emperor")

(solved.ac 티어: 골드 4)