백준(BOJ) 14676 영우는 사기꾼? C++ 풀이

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

14676번: 영우는 사기꾼?

풀이에 이용된 알고리즘: 위상정렬(의 개념)

 

스타크래프트에서 아이디어를 얻은 문제로 보인다ㅋㅋㅋ

 

실제 해당 게임에서도 어떤 건물을 짓기 위해서 미리 건설되어야 하는 다른 건물들이 있다.

 

이 문제에서도 그런 조건을 만족하며 상대방의 건물 건설/파괴 로그에 이상한 점이 있는지 즉, 치트키를 몰래 사용했는지 확인하는 문제이다.

 

어떤 작업의 순서와 관련돼 보여서 처음에는 "위상 정렬"을 떠올렸다.

 

그리고 이어서, X Y라는 입력이 Y를 짓기 위해서 X가 필요하다는 것을 의미하는 간선이라고 할 때 Y를 짓기 위해서 필요한 건물들을 기록해두고(즉, 간선을 뒤집어서 입력 받고) 어떤 건물 target을 짓기 위해서 필요한 source들 중 건설이 안되어있는 경우가 있다면 Lier를 출력하게 하거나, 단 한개도 지어져있지 않은 건물 target을 파괴하는 경우가 로그에서 발견된다면 Lier를 출력하게 하는 구현을 통해서 간단히 해결할 수 있을 것이라고 생각했다.

 

위 방법을 이용했더니 시간 초과가 발생했다... X Y라는 입력에서 하나의 X에 대한 Y의 종류가 최대 3개라고 문제에서 주어졌을 뿐, Y를 짓기 위해서 필요한 X는 3개가 아닌 그 이상의 어마 어마한 숫자가 나올 수 있다.

 

따라서 위 방법은 선형 탐색에서 최악의 성능을 보이는 경우가 있을 수 있으므로, 다시 "위상 정렬" 알고리즘 중 진입 차수에 대한 개념을 이용하여 다음과 같이 풀이하였다.

 

1. 처음에 X Y를 입력받을 때 X를 지음으로써 건설할 수 있게 되는 Y들을 adj[x]에 저장한다.

 

2. y를 짓기 위해서 먼저 지어야 하는 건물들의 수를 require[y]에 저장한다.

 

3. target이라는 번호의 건물을 짓기 위해서는, 해당 건물을 짓기 위해 먼저 건설되어야 하는 건물들(선행 건물)의 수 requires[target]과 현재 지어져있는 선행 건물들의 수 inDegrees[target]이 같아야 한다. 이를 어긴다면 치트키를 사용한 것으로 간주한다.

 

4. target이라는 건물을 지으면 target을 지음으로써 건설할 수 있는 건물들 next의 진입 차수를 증가한다.

단, target이 존재하지 않다가 지어진 경우에만 위 조건을 적용한다.(지었다가 파괴되었다가 다시 짓는 경우에도 해당된다.)

 

5. target을 파괴할 때는 하나 이상 지어져있는 경우에만 파괴가 가능하고, 이를 어긴다면 치트키를 사용한 것이므로 Lier 출력 후 프로그램 종료한다.

 

6. target이라는 건물을 파괴할 때는, target을 지음으로써 건설할 수 있는 건물들의 inDegrees를 1 감소한다.

단, target이 아예 존재하지 않게 된 경우에만 위 조건을 적용한다.(2개 이상 지어진 경우에서 파괴된 경우에는 여전히 target이 존재하는 것이므로 위 조건을 적용x)

 

위 과정 중 설명이 부족한 부분이 있을 수 있는데 아래의 코드와 비교해보면서 분석하는 걸 추천한다.

 

/* BOJ 14676 영우는 사기꾼 */
 
#include <iostream>
#include <functional>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <cmath>
#include <string.h>
#include <vector>
 
using namespace std;
 
#define endl '\n'
 
typedef long long ll;
 
int n, m, k;
int inDegree[100001], requires[100001], constructed[100001];
vector<int> adj[100001];
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    //freopen("input.txt", "r", stdin);
 
    cin >> n >> m >> k;
 
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b); // b를 짓기위해서는 a가 필요함을 의미
        requires[b]++;       // b를 짓기위해서 필요한 건물들의 수 계산
    }
 
    for (int i = 0; i < k; i++)
    {
        int oper, target;
        cin >> oper >> target;
 
        if (oper == 1) // target을 건설하는 경우
        {
            if (inDegree[target] != requires[target])
            {
                cout << "Lier!" << endl;
                return 0;
            }
 
            constructed[target]++;
 
            if (constructed[target] == 1) // 처음 건설한 경우에는
            {
                for (int next : adj[target])
                    inDegree[next]++; // 연관 건물들의 진입 차수 증가
            }
        }
        else // target을 파괴하는 경우
        {
            if (constructed[target] == 0)
            {
                cout << "Lier!" << endl;
                return 0;
            }
            else
            {
                constructed[target]--;
                if (constructed[target] == 0)
                {
                    for (int next : adj[target])
                        inDegree[next]--;
                }
            }
        }
    }
 
    cout << "King-God-Emperor" << endl;
 
    return 0;
}