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

문제 링크

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

문제 요약

1. 게임 설명: '우주전쟁' 게임은 1대1 RTS 게임으로, 각 플레이어는 정해진 건설 순서에 따라 건물을 짓고 유닛을 생성합니다.
2. 건물 건설 순서: 특정 건물을 짓기 위해서는 선행 건물이 먼저 지어져야 합니다. 예를 들어, 건물 4번은 2번과 3번이 지어진 후에만 지을 수 있습니다.
3. 중복 건설 가능: 모든 건물은 여러 번 지을 수 있습니다.
4. 최대 영향 제한: 한 건물은 최대 3개의 다른 건물에만 영향을 미칩니다.
5. 치트키 사용 판별: 영우의 게임 기록에서 치트키를 사용했는지 확인하는 것이 목적입니다. 치트키는 특정 건물의 선행 조건이 충족되지 않았는데도 건물을 지을 수 있게 하며, 지어지지 않은 건물을 파괴하려고 하면 치트키로 간주됩니다.

정답 코드

import sys
n, m, k = map(int, sys.stdin.readline().split())
route =[[] for _ in range(n+1)]
indegree = [0] * (n+1)

for i in range(m):
    s, d = map(int, sys.stdin.readline().split())
    route[s].append(d)
    indegree[d] +=1 

built = [0] * (n+1)

for i in range(k):
    command, building = map(int, sys.stdin.readline().split())
    if command == 1:
        if indegree[building] != 0:
            print("Lier!")
            exit()

        if built[building] == 0:
            for j in route[building]:
                indegree[j] -= 1
                
        built[building] += 1
    else:
        if built[building]<=0:
            print("Lier!")
            exit()        
        built[building] -= 1
        if built[building] == 0:
            for j in route[building]:
                indegree[j] += 1

print("King-God-Emperor")

배웠던 부분

초기 코드:

• route 리스트로 선행 건물의 리스트를 저장합니다.
• 특정 건물을 지을 때, 해당 건물의 선행 건물들이 지어졌는지 확인하기 위해 매번 route[building] 리스트를 순회하면서 확인했습니다.
• 이 방식은 매번 반복문을 통해 선행 조건을 검사해야 하기 때문에 비효율적이며, 특정 건물의 선행 건물이 많을수록 검사 시간이 길어질 수 있습니다.

개선 코드 설명: indegree 배열 사용을 통한 효율화

1. indegree 배열 도입:
   • 각 건물에 대해 몇 개의 선행 건물이 필요한지 진입 차수로 표현하여, 특정 건물의 선행 조건을 바로 확인할 수 있게 했습니다.
   • indegree[b]가 0이면 b 건물을 지을 수 있고, 0이 아니면 선행 조건이 만족되지 않아 지을 수 없습니다. 이를 통해 선행 건물 리스트를 반복해서 확인할 필요 없이, 단일 값 비교로 조건을 확인하게 되어 효율성이 크게 향상되었습니다.
2. 건설 및 파괴 시 indegree 업데이트:
   • 특정 건물이 처음 지어질 때 그 건물과 연결된 후속 건물들의 indegree 값을 1씩 감소시켜 선행 조건을 만족시키는 형태로 업데이트합니다.
   • 반대로, 마지막으로 건물이 파괴되면 후속 건물의 indegree 값을 1씩 증가시켜 선행 조건을 다시 되돌리는 방식입니다.
   • 이를 통해 건물이 여러 번 지어지거나 파괴되더라도, 처음과 마지막 상황에서만 indegree를 업데이트하여 불필요한 연산을 줄이는 최적화가 이루어졌습니다.
3. 조건 위반 시 즉시 종료:
   • 치트키 상황을 만나면 즉시 exit()를 호출하여 프로그램을 종료하고, 결과를 출력하도록 했습니다.
   • indegree로 선행 조건을 관리하므로, 조건 위반 여부를 더 빠르게 판별할 수 있고, exit()를 사용하여 추가적인 검사나 연산을 수행하지 않고 바로 종료합니다.