[JAVA]14676 영우는 사기꾼? 위상정렬 골드3

 📚 문제  

14676번: 영우는 사기꾼?

🔍 아이디어  

오랜만에 풀어본 위상정렬 문제였습니다.

https://lahezy.tistory.com/40 (제가 과거에 작성한 위상정렬 관련 글입니다)

위상정렬 Topology Sort, 백준 1766 문제집(Java)

기존의 위상정렬문제와의 차이점은 건물을 여러 개 건설할 수 있고 파괴할 수 있습니다.

 

우선 입력으로  x -> y에 대해서 y에 대한 진입 차수를 +1 시키고 indegree [y]++

x에서 나가는 y에 대해서 저장합니다.  outGraph.get(x). add(y);

 

모든 입력이 끝난 이후에는 실행한 코드 명령어를 확인하며 거짓말을 치는지 확인합니다.

 

- 건설하는 경우

        - 우선 indegree가 0인지 확인하여 건물을 건설할 수 있는지 확인합니다.

            -  만약 indegree가 0이라면 해당 건물을 건설하기 위해 만족해야 할 다른 건물들이 모두 건설된 것이므로 이번 건물을 지을 수 있습니다.

        -  처음 건설하는 건물인 경우

            -  해당 건물을 건설함으로 인하여지을 수 있는 다음 건물들에 대해 indegree(진입차수)를 하나 감소 시켜줍니다.

        -  이후에는 그냥 건물 개수만 +1 시켜주면 됩니다. (이미 건물이 있는 경우에는 앞에서 체크해서 확인하지 않는다)

 

- 파괴하는 경우

    - 건물이 만약 한 개인 경우

        - 해당 건물은 건설해야만 건설할 수 있는 다음 건물들에 대해서 indegree(진입차수)를 하나씩 증가시켜 줍니다.

            -  (해당 건물이 있어야만 다음건물을 건설할 수 있는데, 해당 건물이 파괴되어 다음건물들을 건설하지 못하는 상항 고려)

    - 이후에는 건물 개수만 -1 시켜주면 됩니다.

 

해당문제에서 Lier를 확인하기 위해서 확인해야 할 것은 건설되지 않은 건물을 파괴하려 하는 경우 해당 건물을 건설할 수 없는 경우인데 건설한 경우입니다. 해당 두 가지 경우에만 라이어 임을 판별하여 코드를 작성하였습니다. 

 

📝 풀이 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static StringTokenizer st;
    private static final List<List<Integer>> outGraph = new ArrayList<>();
    private static int[] inDegree;
    private static int n;
    private static int k;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());//건물 종류 갯수
        int m = Integer.parseInt(st.nextToken());//건물 사이 관계의 개수
        k = Integer.parseInt(st.nextToken()); //게임 정보의 개수

        for (int i = 0; i < n; i++) {
            outGraph.add(new ArrayList<>());
        }
        inDegree = new int[n];

        //x를 건설해야 y를 건설 할 수 있음
        while (m-- > 0) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()) - 1;
            int y = Integer.parseInt(st.nextToken()) - 1;

            outGraph.get(x).add(y);
            inDegree[y]++;
        }
        System.out.println(checkLier() ? "Lier!" : "King-God-Emperor");
    }

    private static boolean checkLier() throws IOException {
        int[] buildings = new int[n];
        while (k-- > 0) {
            st = new StringTokenizer(br.readLine());
            int cmd = Integer.parseInt(st.nextToken());
            int index = Integer.parseInt(st.nextToken()) - 1;

            if (cmd == 1) {
                if (inDegree[index] != 0) {//건물을 지울 수 있는지 확인
                    return true; //건물 짓지 못한다 -> 거짓말
                }

                buildings[index]++; //건문을 건설한다.
                if (buildings[index] == 1) { //건물이 하나만 지어진 경우에는
                    for (int next : outGraph.get(index)) { //해당 건물이 지어져서 건설할 수 있는 다음 건물들 
                        inDegree[next]--; 
                    }
                }
            } else {
                if (buildings[index] == 0) return true; //지어지지 않은 건물은 부시려고 함
                if (buildings[index] == 1) { //건물이 하나만 있을 때 부시는 경우 해당 건물이 있어야 존재할 수 있는 건물들에 대해서 다시 1 증가
                    for (int next : outGraph.get(index)) {
                        inDegree[next]++;
                    }
                }
                buildings[index]--; //건물을 부신다.
            }
        }
        return false; //거짓말을 치지 않음
    }
}