문제 이해

A라는 건물을 짓기 위해서는 사전에 지어져야 하는 건물이 모두 지어져 있어야 한다.
단, B ⇒ A ⇒ C 관계성을 가질 때, B를 짓고 A를 지었다면, 이후 B가 파괴되었더라도 A가 파괴되지 않은 이상 C는 지을 수 있다.

영우는 건물을 세울 것이며, 영선이는 건물을 파괴시킬 것이다.

게임 로그를 보고, 게임 로그가 정상적으로 수행 가능한 경우 'King-God-Emperor'를, 게임 로그대로 수행 불가능한 경우 'Lier!'를 출력하는 문제이다.

---

문제 풀이

문제에서 나온 그림만 보고서도 이 그래프는 DAG 그래프라는 것을 눈치 챘을 것이다.

문제는 "건물을 파괴 가능하다"이다.

즉, 이전까지는 한 번 건물이 지어졌다면 무조건 다음 건물로 넘어갔지만, 이 문제의 경우 특정 건물을 지을 때 처리해야 할 것이 좀 많다.

1. 사전에 지어져야 할 건물들이 모두 지어져 있는가를 확인한다.

2. 이 건물을 지어야 지을 수 있는 건물들(A ⇒ B에서 B건물)에 영향을 주는가 아닌가

또한 건물을 파괴할 때도, 해당 건물이 존재하는지 여부를 확인해야 하며, 같은 건물이 여러 개 지어질 수 있다는 점도 눈여겨 봐야 한다.

따라서, 이번 문제에서는 input 배열 뿐만이 아닌, 해당 건물이 몇 개 지어져있는지, 그리고 사전에 지어져야 할 건물들이 몇 개 지어졌는지에 대한 정보를 저장할 공간이 필요하다.

---

코드

import java.io.*;
import java.util.*;

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N, E, L;
	static ArrayList<Integer>[] need; 
    // need[A] = {B,C,D} : 건물 B,C,D를 짓기 이전 
    //                     A는 사전에 지어져 있어야 한다는 것을 의미
	static int[] num;
    // num[A] : A 건물이 몇 개 지어져 있는가
	static int[] input;
    // input[A] : A를 짓기 위해 몇 개의 사전 건물을 더 지어야 하는가
    // 즉, input[A] = 0이 되어야지만 A 건물을 지을 수 있다.

	public static void main(String[] args) throws IOException {
		FastReader sc = new FastReader();
		
		N = sc.nextInt();
		E = sc.nextInt();
		L = sc.nextInt();
		
		num = new int[N+1];
		need = new ArrayList[N+1];
		input = new int[N+1];
		
		for(int i =1;i<N+1;i++) {
			need[i] = new ArrayList<>();
		}
		
		for(int i=0;i<E;i++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			
			need[start].add(end);
			input[end]++;
		}
		
		for(int i =0;i<L;i++) {
			int type = sc.nextInt();
			int build = sc.nextInt();
			
			if(type==1) { // 건물 짓기
				num[build]++;
				
				if(input[build]!=0) {
                    // input 배열의 정의 상 input[build] = 0일 때만 
                    // build 건물이 지어질 수 있다.
                    // 따라서, build를 지을 수 없는데 지어야 하므로 
                    // 치트키를 사용했다.
					System.out.println("Lier!");
					return;
				}
				
				if(num[build]==1) {
                    // num[build] = 1이라는 것은, 원래 build가 없었지만 
                    // 새로 생성되었다는 의미이다.
                    // 따라서, build 건물을 사전에 지어져야 할 건물로
                    // 가지고 있는건물들의 input값을
                    // 1씩 감소 시켜준다.
					for(int s:need[build]) {
                        // build -> s 관계
						input[s]--;
					}
				}
			}
			else { // 건물 파괴
				num[build]--;
				
				if(num[build]<0) {
                    // 건물의 개수는 음수가 될 수 없다. 따라서 치트키를 사용했
					System.out.println("Lier!");
					return;
				}
				
				if(num[build]==0) {
                    // 건물의 개수가 0개라는 것은 건물이 아예 
                    // 파괴되었다는 것을 의미한다.
                    // 즉, build를 사전에 지어져야 할 건물로 가지고 있는 
                    // 건물들의 input값이 1씩 증가해야 한다.
					for(int s:need[build]) { 
                        // build -> s 관계
						input[s]++;
					}
				}
			}
		}
		
		System.out.println("King-God-Emperor");
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

---

결과

• 3,4번째 줄 시간 초과 : 최대한 사용하는 공간을 줄이기 위해서 input[] 배열을 사용하지 않고, ArrayList를 조금 변형시켜 문제를 풀어보았다. 하지만 list의 길이도 길어질 뿐더러 num을 통해 검사하는 과정도 추가되어 많은 과정이 추가되었고, 이로 인해 시간 초과가 발생하였다.

• 2번째 줄 시간 초과 : 큰 따옴표 하나를 생략하여 발생하였다.