[백준] 14676번 : 영우는 사기꾼? Gold3(골드3) - JAVA[자바]

[Gold III] 영우는 사기꾼? - 14676

문제 링크

성능 요약

메모리: 63620 KB, 시간: 384 ms

분류

방향 비순환 그래프, 그래프 이론, 구현

제출 일자

2024년 6월 6일 11:45:17

문제 설명

영선이와 영우는 최근 ‘우주전쟁’ 이라는 게임을 시작했다. ‘우주전쟁’은 1대1로 하는 RTS(실시간 전략 게임) 게임으로, 각 플레이어는 건물을 건설하고, 건물에서 유닛을 생성하여 싸운다. ‘우주전쟁’은 건물을 짓는 순서가 정해져 있는데, 예를 들어 건물들이 다음과 같은 관계도를 가진다고 할 때,

2, 3번 건물은 반드시 1번 건물이 건설된 상태여야 지어질 수 있고, 4번 건물은 반드시 2, 3번 건물이 건설된 상태여야 지어질 수 있다. 단 4번 건물은 1번 건물과는 직접적인 연관이 없기 때문에 1번 건물이 없다고 하더 라도 4번 건물은 건설이 가능하다. 이때 1번 건물은 2, 3번 건물에 영향을 미친다고 할 수 있고, 2, 3번 건물은 4번 건물에 영향을 미친다고 할 수 있다. 또한 모든 건물들은 중복 건설이 가능하다. ‘우주전쟁’ 게임의 제작사 인 ‘얼음폭풍’사는 게임의 밸런스를 유지하기 위해 한 건물은 최대 3개의 건물에게만 영향을 미치도록 하였다. 또 ‘우주전쟁’ 게임에는 치트키가 하나 있는데, 이 치트키를 사용하면 원하는 건물을 마음대로 설치할 수 있다. 하지만 이 치트키를 사용하면 너무나 쉽게 게임에서 이길 수 있기 때문에 영선이와 영우는 서로 치트키를 쓰지 않기로 약속했다. 하지만 이상하게도 영우는 영선이와의 게임에서 모두 승리하였고, 그런 영우를 이상하게 여긴 영선이는 영우의 건물 건설/파괴 정보를 가져왔다. (치트키로 건설한 건물은 건설 정보에 들어가지 않는 다.) 영우의 게임정보를 보고 영우가 치트키를 사용했는지 판단하는 프로그램을 만들어 영선이를 도와주자.

입력

프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 건물의 관계인 X Y 가 차례대로 중복 없이 주어진다. (X를 건설해야 Y를 건설할 수 있음.) (1 ≤ X, Y ≤ N) 다음 줄부터 K줄에 걸쳐 영우의 게임 정보가 다음과 같이 주어진다. (1 ≤ a ≤ N)

• 1 a(영우가 a번 건물을 1개 건설함)
• 2 a(영우의 a번 건물이 1개 파괴됨)

출력

프로그램의 출력은 표준 출력으로 한다. 영우가 정상적으로 건물을 건설하거나, 건설한 만큼의 건물만 파괴되 었다면 ‘King-God-Emperor’를. 건설할 수 없는 건물을 건설하거나, 건설한적 없는 건물이 파괴되었다면 ‘Lier!’ 를 출력하자.

접근 방법

1. 건물 생성시 해당 건물의 진입차수가 0이면 생성 가능하다. <-> 만약 0이 아니라면 치트를 사용한 것
2. 처음 생성한 건물이라면 연결된 노드들의 진입차수를 1씩 감소 시켜줌
3. 파괴시 만들어진 건물의 개수가 0보다 크면 생성이 가능하다. ( 0이라면 만들어진 건물이 없음 )
4. 파괴시 남아있는 해당 건물이 존재하지 않는다면 연결된 노드들의 진입차수를 1씩 증가 시켜준다.

 

- 위상정렬과 비슷한 개념의 문제로 생각하고 풀면 쉽다.

 

풀이 코드

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

/**
 * 문제 : BOJ_14676_영우는 사기꾼?
 * 메모리: 63620KB
 * 시간: 384ms
 * 접근 방법
 * 1. 건물 생성시 해당 건물의 진입차수가 0이면 생성 가능하다. <-> 만약 0이 아니라면 치트를 사용한 것
 * 2. 처음 생성한 건물이라면 연결된 노드들의 진입차수를 1씩 감소 시켜줌
 * 3. 파괴시 만들어진 건물의 개수가 0보다 크면 생성이 가능하다. ( 0이라면 만들어진 건물이 없음 )
 * 4. 파괴시 남아있는 해당 건물이 존재하지 않는다면 연결된 노드들의 진입차수를 1씩 증가 시켜준다.
 */
public class Main {
    static class Node {
        int idx;
        Node next;

        public Node(int idx, Node next) {
            this.idx = idx;
            this.next = next;
        }
    }

    static Node[] graph;
    static int[] inDegree, created;
    static final String CHEAT = "Lier!";
    static final String NO_CHEAT = "King-God-Emperor";

    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());

        // Input
        inDegree = new int[N + 1];
        created = new int[N + 1];
        graph = new Node[N + 1];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            graph[from] = new Node(to, graph[from]);
            inDegree[to]++;
        }// Input

        int i = 0;
        for (; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            int command = Integer.parseInt(st.nextToken());
            int idx = Integer.parseInt(st.nextToken());

            // 건물 건설
            if (command == 1 ) {
                // 연결된 건물이 있는데 생성 하려고 한다면 오류
                if(inDegree[idx] != 0){
                    break;
                }
                createBuilding(idx);
            }
            // 건물 파괴
            else if (command == 2) {
                // 만들어진 건물이 없는데 파괴하려고 한다면 오류
                if(created[idx] == 0){
                    break;
                }
                destroyBuilding(idx);
            }
        }

        System.out.println(i == K ? NO_CHEAT : CHEAT);
    }

    // 파괴 후 만들어진 건물이 0개면 연결된 노드들의 진입 차수 증가
    private static void destroyBuilding(int idx) {
        created[idx]--;
        if (created[idx] == 0) {
            for (Node tmp = graph[idx]; tmp != null; tmp = tmp.next) {
                inDegree[tmp.idx]++;
            }
        }
    }

    // 생성 후 처음 생성한 건물이라면 진입 차수 감소
    private static void createBuilding(int idx) {
        created[idx]++;
        if (created[idx] == 1) {
            for (Node tmp = graph[idx]; tmp != null; tmp = tmp.next) {
                inDegree[tmp.idx]--;
            }
        }
    }
}