[백준] 14676. 영우는 사기꾼?(Java)

문제

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

 

풀이

해당 문제는 선행 조건에 따라서 건물을 지을 수 있는지 체크하고

이미 지어진 건물이 있어서 건물을 파괴할 수 있는지 체크하는 문제입니다.

 

선행조건에 따라 해결하는 문제이다보니 위상정렬을 이용합니다.

또한 건물이 지어진 개수가 몇개인지 파악하기 위한 배열을 생성합니다.

 

간선을 이어주는 과정에서

진입 차수에 해당하는 두번째 인자의 경우 in[b] ++ 해줍니다.

 

쿼리에 맞게

type이 1이고 타겟이 cur이라면

in[cur]은 반드시 0이어야지 건물 생성이 가능합니다.

이러한 이유는 선행조건(해당 건물을 짓기 위해 미리 지어야 하는 건물)이 달성되어야지만 지을 수 있기 때문입니다.

in[cur]가 0이라는 것은 선행조건을 모두 달성했다는 의미입니다.

 

따라서, createdCnt[cur]을 ++하고, 해당 건물을 선행조건으로 여기는

다음 건물에 대해서 진입차수를 1 감소시켜 줍니다.

 

이외의 경우는 모두 false 케이스입니다.

false 케이스인 경우 순회를 멈춥니다.

 

type이 2일 때는 파괴할 건물이 이미 생성되어 있어야 하므로 createdCnt[cur]가 0보다 커야 합니다.

따라서, 생성된 건물을 1개 파괴 하고

이후 남은 개수가 0이라면, 해당 건물을 선행조건으로 여기는

다음 건물에 대해서 진입차수를 1 증가시켜 줍니다.

 

이외의 경우는 모두 false 케이스입니다.

false 케이스인 경우 순회를 멈춥니다.

 

순회를 마치고 true 케이스와 false 케이스에 맞게

정답을 출력해줍니다.

 

코드

74,984 KB / 580 ms

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

public class Main {
    static int[] createdCnt, in;
    static List<Integer>[] list;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken()); // 노드 수
        int M = Integer.parseInt(st.nextToken()); // 간선 수
        int K = Integer.parseInt(st.nextToken()); // 쿼리

        in = new int[N+1];
        createdCnt = new int[N+1];
        list = new ArrayList[N+1];

        for(int i = 1 ; i <= N ; i ++)
            list[i] = new ArrayList<>();

        for(int i = 0 ; i < M ; i ++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            list[a].add(b);
            in[b] ++;
        }

        boolean flag = true;
        for(int i = 0 ; i < K ; i ++){
            st = new StringTokenizer(br.readLine());
            int type = Integer.parseInt(st.nextToken());
            int cur = Integer.parseInt(st.nextToken());

            // 건물을 건설
            if(type == 1 && in[cur] == 0){
                createdCnt[cur] ++;

                // cur이 선행되어야 하는 건물에 대해 => 해금(cur 생성 완료에 해당하는 조치)
                if(createdCnt[cur] == 1){
                    for(int next: list[cur]) in[next]--;
                }
            }
            // 건물을 파괴 => 해금을 다시 원래대로 복기
            else if(type == 2 && createdCnt[cur] > 0){
                createdCnt[cur] --;

                if(createdCnt[cur] != 0) continue;

                // 원래대로 돌리기
                for(int next: list[cur]) in[next] ++;
            }
            // 건설 or 파괴가 불가능하다면
            else{
                flag = false;
                break;
            }
        }

        System.out.println(flag ? "King-God-Emperor" : "Lier!");
    }
}