[BOJ/Gold 3] 백준 14676 영우는 사기꾼?(C++)

문제 링크

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

14676번: 영우는 사기꾼?

문제

영선이와 영우는 최근 ‘우주전쟁’ 이라는 게임을 시작했다. ‘우주전쟁’은 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

4 4 5
1 2
1 3
2 4
3 4
1 1
1 2
1 3
2 1
1 4

예제 출력 1

King-God-Emperor

예제 입력 2

3 2 2
1 2
2 3
1 1
2 2

예제 출력 2

Lier!

예제 입력 3

3 2 5
1 2
2 3
1 1
1 2
1 2
2 2
1 3

예제 출력 3

King-God-Emperor

알고리즘 분류

• 구현
• 위상 정렬

풀이

처음에 제출했을 때 시간 초과가 발생해서 잠깐 구글링을 통하여 한 건물을 건설하는 데 필요한 건물의 개수 Build_Able을 저장하는 배열을 통하여 해결하였다.

A건물을 건설할 때, B, C 건물이 필요하다면 Build_Able[A]는 2로 시작하고, 건물 B, C가 건설되었다면 Build_Able[A]는 0이 된다. Build_Able[]이 0이 되었을 때에만 해당 건물을 건설할 수 있도록 하였다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100005
#define INF 1e9

using namespace std;
int N, M, K;
vector<int> Condition[MAX];
int Build[MAX];
int Build_Able[MAX];
bool answer = true;

int main() {
	FIRST
	cin >> N >> M >> K;
	for (int i = 0; i < M; i++) {
		/*
			X건물을 건설해야 Y건물을 건설할 수 있다.
			X건물이 존재하는 것이 조건인 건물들을 Condition[X] 벡터에 저장한다.
		*/
		int X, Y;
		cin >> X >> Y;
		Condition[X].push_back(Y);
		Build_Able[Y]++; // Y건물을 건설하기 위해 필요한 건물, 0이 되어야 Y를 건설할 수 있음.
	}
	for (int i = 0; i < K; i++) {
		int Cmd, A;
		cin >> Cmd >> A;
		if (Cmd == 1) { // A번 건물을 1개 건설함
			if (Build_Able[A] > 0) { // A번 건물을 건설하기 위해 필요한 건물이 다 건설되어 있지 않다면
				// 영우는 치트키를 사용한 것이다.
				answer = false;
				break;
			}
			else { // 필요한 건물이 다 건설되었다면
				Build[A]++; // A번 건물을 건설한다. 여기서 건물이 여러개일 수 있으므로 boolean이 아닌 정수형으로 선언하였다.
				if (Build[A] == 1) { 
					/*
						A번 건물이 하나만 있어도 B, C번 건물을 건설할 수 있으므로,
						A번 건물이 하나만 건설되어 있을 때에만
						A번 건물을 필요로 하는 건물들의 조건을 수정한다.
					*/
					for (int j = 0; j < Condition[A].size(); j++) {
						int Cond = Condition[A][j];
						Build_Able[Cond]--;
					}
				}
			}
		}
		else if (Cmd == 2) { // A번 건물이 1개 파괴됨
			if (Build[A] == 0) { // A번 건물이 건설되어 있지 않다면 영우는 치트키를 사용한 것이다.
				answer = false;
				break;
			}
			else { // A번 건물이 1개 이상 존재한다면
				Build[A]--; // A번 건물을 파괴한다.
				if (Build[A] == 0) { // A번 건물이 0개, 즉 사라졌다면 B, C번 건물은 필요한 조건을 하나 잃어버린 것이다.
					for (int j = 0; j < Condition[A].size(); j++) {
						int Cond = Condition[A][j];
						Build_Able[Cond]++;
					}
				}
			}
		}
	}
	if (answer) {
		cout << "King-God-Emperor" << "\n";
	}
	else {
		cout << "Lier!" << "\n";
	}

	return 0;
}