(C++) - 백준(BOJ) 14676번 : 영우는 사기꾼?

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

14676번: 영우는 사기꾼?

위상정렬 문제였습니다.

 

 

📕 풀이방법

📔 입력 및 초기화

일차원 배열 선언 : 건설여부를 저장할 buildCheck 진입차수를 저장할 indegree를 선언합니다.

입력받은 정보를 토대로 단방향 인접리스트 그래프 graph를 생성합니다 그리고 진입차수를 저장합니다.

치트를 썻는지의 여부 bool형 변수 isCheat를 선언합니다.

 

 

📔 풀이과정

 x를 건설할 경우 x가 선제조건으로 지을 수 있는 인접건물들이 해금됩니다. 반대로 x건물을 파괴할 경우 잠깁니다. 이 두 경우에서 줄기를 잡고 출발합니다.

k만큼 op, x를 입력받습니다.

 1. op == 1이면 x번 건물 건설을 의미합니다.

  1-1. 만약 진입차수가 0이 아니라면 (양수 또는 음수) 치트를 써 건설한 것이 되므로 isCheat = true입니다.

  1-2. 진입차수가 0이라면 지을 수 있습니다.

    1-1-1. 하지만 이미 지어져 있는 경우가 있을 수 있습니다. 따라서 이 경우에는 다른 건물들이 이미 해금되어있을 것이므로 다른 건물들에 대한 진입차수를 낮출 필요없고 건물을 지어줍니다.(buildCheck[x]++) 

    1-1-2. 일반적인 경우 주변 건물들을 해금시키고 건물을 지어줍니다.

 

 2. op == 2면 x번 건물 제거를 의미합니다.

  2-1. 건물이 지어진 상태가 아니면 cheat를 사용한 것이므로 isCheat는 true입니다.

  2-2. 건물이 지어져 있는 정상적인 상태라면 buildCheck[x]--해줍니다. 이 때 같은 건물이 여러개일 수 있기 때문에 해당 건물이 하나도 없을 때에만 주변건물들을 잠가줍니다.

 

 

 

📔 정답출력

 isCheat가 true라면 King-God-Emperor를 아니라면 Lier를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
int indegree[100001], buildCheck[100001];
vector <int> graph[100001];
bool isCheat;
int main(){
    cin >> n >> m >> k;
    for(int i = 0,x,y; i < m; i++){
        cin >> x >> y;
        graph[x].push_back(y);
        indegree[y]++;
    }
    for(int i = 0,op,x; i < k; i++){
        cin >> op >> x;

        if(isCheat) continue;

        if(op == 1){ //건설
            if(indegree[x]) isCheat = true;
            else{
                if(buildCheck[x]++) continue;
                for(auto next : graph[x]) indegree[next]--;
            }
        }

        else{
            if(buildCheck[x] == 0) isCheat = true;
            else {
                buildCheck[x]--;
                if(buildCheck[x] > 0) continue;
                for(auto next : graph[x]) indegree[next]++;
            }
        }

    }
    if(isCheat) cout << "Lier!";
    else cout << "King-God-Emperor";
}