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

문제 링크: https://www.acmicpc.net/problem/14676

14676번: 영우는 사기꾼?

1. 주의할 점

- 위상정렬에 대해 알고 있어야 한다

- 해당 건물이 여러개 지어질 수도 있다

 

2. 구현

- Li[]를 통해 선행관계를 저장한다

- Building[]을 통해 각 건물이 지어진 수를 저장한다

- Conn[]을 통해 해당 건물을 짓기위해 선행되어야 하는 건물 수를 저장한다

- 각 조건에 따라 치트키 사용여부를 판단한다

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

class Main {
    static int node,edge,k;
    static List<Integer> li[];
    static int building[];      //지은 건물의 수
    static int conn[];
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    StringTokenizer st = new StringTokenizer(br.readLine());
	    node = Integer.parseInt(st.nextToken());
	    edge = Integer.parseInt(st.nextToken());
	    k = Integer.parseInt(st.nextToken());
	    //초기화
	    li = new List[node+1];
	    building = new int[node+1];
	    conn = new int[node+1];
	    for(int i=1;i<=node;i++)
	        li[i] = new ArrayList<>();
	        
	    for(int i=0;i<edge;i++){
	        st = new StringTokenizer(br.readLine());
	        int first = Integer.parseInt(st.nextToken());
	        int sec = Integer.parseInt(st.nextToken());
	        li[first].add(sec);
	        conn[sec]++;
	    }
        String answer = "King-God-Emperor";
        for(int i=0;i<k;i++){
            st = new StringTokenizer(br.readLine());
	        int order = Integer.parseInt(st.nextToken());       //1: 건설, 2:파괴
	        int idx = Integer.parseInt(st.nextToken());
	        if(order==1){
	            if(conn[idx]>0){ //건설 불가능
	                answer = "Lier!";
	                break;
	            }
	            else{
	                building[idx]++;
	                if(building[idx]==1 && li[idx].size()>0){
	                    for(int j=0;j<li[idx].size();j++){
	                        int next = li[idx].get(j);
	                        conn[next]--;
	                    }
	                }
	            }
	        }
	        else{       //파괴
	            if(building[idx]==0) {      //건설한 적 없는 건물
	                answer = "Lier!";
	                break;
	            }
	            else{
	                building[idx]--;
	                if(building[idx]==0 && li[idx].size()>0){
	                    for(int j=0;j<li[idx].size();j++){
	                        int next = li[idx].get(j);
	                        conn[next]++;
	                    }
	                }
	            }
	        }
        }
		System.out.print(answer);
	}
}